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.

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

share|improve this question
6  
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
3  
We have linear time algorithms to detect planarity, so the simplest could actually be not that simple... –  Aryabhata Feb 17 '11 at 20:10
2  
@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
3  
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

1 Answer 1

up vote 1 down vote accepted

To give this old question an answer, I repeat some good points of the comments (with additions):

  1. Kuratowski's Theorem tells us that a finite simple graph is planar if and only if it has no minor isomorphic to $K_5$ or $K_{3,3}$. If I remember correctly, there are also versions for infinite graphs adding some additional constraints (like the cardinality of the vertex set is at most the continuum).

  2. For finite graphs there are efficient algorithms to determine planarity.

  3. So for your question, we need to find an infinite graph whose planarity is open. Another possibility would be an infinite series $(G_n)_{n\in\mathbb N}$ of finite graphs, and asking questions like "Are all graphs $G_n$ planar?

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.