"Find a planar embedding or prove that one does not exist"
So went an infamous graph theory problem some years ago... and so it went today while playing level 4 of
Planarity. This game is not hard at level 4, but this time I was stumped! After having no luck for about 5 minutes, I thought maybe I'd just missed something obvious, so I hit "Shuffle Vertices" and tried again. After a second failed effort, I suspected that something was wrong. (Well, actually, I suspected that after the first 30 seconds, but I try hard to resist my natural urge to immediately *blame someone else* when something goes wrong.) Sure enough, my latest time-suck had given me a
non-planar graph. Now, as anyone who's had Discrete Math knows,
Kuratowski's Theorem
states that a graph is non-planar iff it contains a subdivision of (i.e. has as a
minor)
K_5 or K_{3,3}. That is, if we can achieve K_5 or K_{3,3} by contracting edges and deleting stuff, then the graph is not planar.
Figure 1: Undoctored screenshot from Planarity.
Figure 2: Doctored screenshot, with clusters of vertices shown in color. To create K_5, contract all edges/vertices of like color down to a single vertex.
Figure 3: With extraneous stuff deleted, the graph in Figure 2 clearly reduces to this standard single-crossing embedding of K_5.
Really makes me wonder what "algorithm" they're using to generate these things....
HOMEWORK: Does this graph also contain K_{3,3} as a minor?
EDIT: Just read the F.A.Q. below the game. Seems this is a known issue. And here I thought I'd discovered something....
Figure 1: Undoctored screenshot from Planarity.
Figure 2: Doctored screenshot, with clusters of vertices shown in color. To create K_5, contract all edges/vertices of like color down to a single vertex.
Figure 3: With extraneous stuff deleted, the graph in Figure 2 clearly reduces to this standard single-crossing embedding of K_5.
Really makes me wonder what "algorithm" they're using to generate these things....
HOMEWORK: Does this graph also contain K_{3,3} as a minor?
EDIT: Just read the F.A.Q. below the game. Seems this is a known issue. And here I thought I'd discovered something....