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.

$\endgroup$
  • 2
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Qiaochu Yuan Nov 12 '10 at 12:04
  • $\begingroup$ The fundamental group is not very useful in this context, as each finite graph is homotopy equivalent to a bouquet of circles. $\endgroup$ – Robin Chapman Nov 12 '10 at 14:08
4
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Thank you but I was hoping for a proof that was more pure topological, for example by looking at its fundamental group. $\endgroup$ – letitibe Nov 12 '10 at 12:21
  • 1
    $\begingroup$ @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). $\endgroup$ – Qiaochu Yuan Nov 12 '10 at 12:49
3
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy