# What is the simplest graph that is not know to be planar or non-planar?

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

-
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
We have linear time algorithms to detect planarity, so the simplest could actually be not that simple... –  Aryabhata Feb 17 '11 at 20:10
@Chris: There could be infinite graphs where the status is unknown. –  mjqxxxx Feb 17 '11 at 20:13
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
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. 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).
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?