5
$\begingroup$

A graph G is planar if and only if xxx.

What can xxx be substituted for? Note that this is from a topological POV so a graph is a 1-dim cw complex and I guess the fundamental group should be used somehow.

  • 2
    http://en.wikipedia.org/wiki/Planar_graph#Kuratowski.27s_and_Wagner.27s_theorems2010-11-12
  • 0
    The fundamental group is not very useful in this context, as each finite graph is homotopy equivalent to a bouquet of circles.2010-11-12

3 Answers 3

4

Please refer Kuratowski's theorem on Planar graphs.

Kuratowski: A graph $G$ is planar iff $G$ does not contain a sub division of $K_{5}$ or $K_{3,3}$.

  • 0
    Thank you but I was hoping for a proof that was more pure topological, for example by looking at its fundamental group.2010-11-12
  • 1
    @letitbe: you can't tell whether a graph is planar from its fundamental group. The fundamental group is free and its rank depends only on the number of vertices and edges in the graph (if it is connected).2010-11-12
3

There are lots of characterizations of planar graphs, e.g. Kuratowski's theorem as already mentioned. Another is Whitney's theorem that a finite graph $G$ is planar if and only if the dual matroid to the matroid of $G$ is graphic (also comes from a graph).

2

A very good treatment of when a graph can be embedded in the plane and more generally into other surfaces is given by the excellent book:

Graphs on Surfaces by Bojan Mohar and Carsten Thomassen (John Hopkins U. Press, 2001)