... Or perhaps, what are some interesting examples of simple graphs that are not known to be planar or non-planar?
What is the simplest graph that is not know to be planar or non-planar?
2
$\begingroup$
graph-theory
-
0@Chris... well, I guess that answers it. I was unaware of an algorithm that would determine planarity in general. – 2011-02-18
1 Answers
2
To give this old question an answer, I repeat some good points of the comments (with additions):
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).
For finite graphs there are efficient algorithms to determine planarity.
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?