... 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
-
6There'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. – 2011-02-17
-
3We have linear time algorithms to detect planarity, so the simplest could actually be not that simple... – 2011-02-17
-
2@Chris: There could be infinite graphs where the status is unknown. – 2011-02-17
-
1If there is a linear time algorithm, then the question is just as meaningful as «what's the biggest number we can write?». – 2011-02-17
-
0mjqxxxx makes a good point however, simple does not necessarily mean finite. – 2011-02-17
-
3Kuratowski'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)? – 2011-02-17
-
1@mjq: Not isomorphic, but [homeomorphic](http://en.wikipedia.org/wiki/Homeomorphism_%28graph_theory%29). – 2011-02-17
-
0@mjqxxxx Unfortunately, this comes down to your definitions of 'natural', and how exactly you define your graphs; the easy version is 'take a graph with vertices $v_n (n\ge0)$ and $w_n (n\ge0)$, (bidirectional) edges from $v_n$ to $w_n$, $v_n$ to $v_{n-1}$ and $v_{n+1}$, and $w_n$ to $w_{n-1}$ and $w_{n+1}$; then add e.g. edges from $v_n$ to $w_{n-1}$ and $w_{n+1}$ and from $w_n$ to $v_{n-1}$ and $v_{n+1}$ iff $n$ is an even number not the sum of two primes'. AFAIK relatively few infinite graphs receive much attention aside from the Random Graph, which is of course trivially non-planar. – 2011-02-17
-
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?