Tell me more ×
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.
up vote 1 down vote favorite

... Or perhaps, what are some interesting examples of simple graphs that are not known to be planar or non-planar?

share|improve this question
5  
There's an efficient (cubic in the number of vertices) algorithm for determining planarity of graphs, so I think this is more a matter of who's bothered to check what and how much computer power has been used than interesting mathematics. – Chris Eagle Feb 17 '11 at 20:09
2  
We have linear time algorithms to detect planarity, so the simplest could actually be not that simple... – Aryabhata Feb 17 '11 at 20:10
1  
@Chris: There could be infinite graphs where the status is unknown. – mjqxxxx Feb 17 '11 at 20:13
1  
If there is a linear time algorithm, then the question is just as meaningful as «what's the biggest number we can write?». – Mariano Suárez-Alvarez♦ Feb 17 '11 at 20:46
2  
Kuratowski's theorem states that a graph is planar iff it contains no subgraph isomorphic to either $K_{3,3}$ or $K_5$. For finite graphs, then, the question is not very interesting. For infinite graphs, it may be difficult to determine whether or not there is a subgraph of the appropriate form. Can anyone exhibit a "natural" example where the question of planarity is equivalent to a known open question (in number theory, say)? – mjqxxxx Feb 17 '11 at 21:20
show 4 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.