Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

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

share|improve this answer
    
Thank you but I was hoping for a proof that was more pure topological, for example by looking at its fundamental group. –  letitibe Nov 12 '10 at 12:21
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). –  Qiaochu Yuan Nov 12 '10 at 12:49

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

share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.