22
$\begingroup$

I've been trying to find out if this graph is planar or not for a while and have really been coming up short when it comes to creating a planar drawing of the graph. My intuition is telling me that it's non-planar, but I cannot find any subgraph of the graph homeomorphic to K3, 3 (by Kuratowski's Theorem). Any help would be greatly appreciated. The graph can be seen below:enter image description here

$\endgroup$
  • $\begingroup$ Aren't there two subgraphs you have to check? $\endgroup$ – dbx Oct 17 '17 at 1:26
  • 3
    $\begingroup$ Yes, but it's pretty obvious that it can't contain K5 as a subgraph. $\endgroup$ – John21 Oct 17 '17 at 1:51
  • $\begingroup$ @dbx To have a subgraph homeomorphic to $K_5$ it would have to have at least $5$ vertices of degree $\ge4,$ wouldn't it? $\endgroup$ – bof Oct 17 '17 at 6:14
  • $\begingroup$ I'm sure you guys are right, I was truly asking :) $\endgroup$ – dbx Oct 17 '17 at 12:18
  • $\begingroup$ @bof For a subdivision of $K_5$ yes, for a $K_5$-minor no. For example, the Petersen graph has a $K_5$-minor: you get $K_5$ if you contract the $5$ edges from the outside cycle to the twisted inside cycle. $\endgroup$ – Misha Lavrov Oct 18 '17 at 15:31
51
$\begingroup$

Although the question has already been thoroughly answered, here is an unusual approach to checking if a graph is planar that I'm very fond of which works well here.

First, we notice that there's a cycle passing through all $12$ vertices:

Hamilton cycle

(This method is only guaranteed to settle the question one way or the other if we find such a cycle, though for a cycle that passes through only most of the vertices it can still be very helpful.)

Now redraw the graph so that this cycle is arranged in a circle:

Cycle as circle

If there's a planar embedding of the graph, this circle has to appear in it somewhere, and so the only choices left to make for how to draw the graph are deciding, for each edge not in the cycle, whether it will be drawn as a chord inside the circle or outside the circle.

But the three highlighted edges all intersect each other. No matter which choices you make for them, either two of them will be on the inside (and intersect) or two of them will be on the outside (and intersect). So there is no planar embedding.

(In general, once the Hamiltonian cycle has been found - if it exists - deciding if the remaining edges can be drawn without crossing is straightforward. Begin with an arbitrary choice and then just make sure that if an edge is on the inside, all the edges it crosses are on the outside, and vice versa.)

$\endgroup$
  • 5
    $\begingroup$ Indeed, the second drawing makes the $K_{3,3}$-subdivision easy to see: since $l$ sees $a$ and $c$ along the cycle and $g$ along the red edge, this naturally suggests that $\{a,c,g\}$ should be the branch vertices for one part of the $K_{3,3}$ and $\{l,b,e\}$ should be the branch vertices for the other part. $\endgroup$ – Gregory J. Puleo Oct 17 '17 at 3:01
  • 5
    $\begingroup$ But checking planarity does not require finding Ham cycle. Planarity is much easier problem. $\endgroup$ – rus9384 Oct 17 '17 at 7:18
  • 3
    $\begingroup$ That's true! This is not a method you'd teach your computer to do on hundreds of vertices. In practice, finding a Hamiltonian cycle by hand, in a relatively small planar graph, is often easy - and you can see that this method would tell us a lot even if we found a cycle only on $10$ or $11$ vertices, though we'd be left with more casework to do. $\endgroup$ – Misha Lavrov Oct 17 '17 at 15:38
  • 2
    $\begingroup$ This is similar in principle to Hopcroft & Tarjan's 1974 "efficient planarity Testing" O(N) algorithm although they look at a hierarchy of cycles formed in each biconnected component (and do not rely on finding a single hamiltonian cycle). A detailed analysis can be found in the "Planarity Testing By Path Addition" Thesis showing how the cycles are generated and chords are added (forming additional child cycles) to either the inside or outside of each parent cycle. $\endgroup$ – MT0 Oct 18 '17 at 10:19
  • 2
    $\begingroup$ You're computing what's sometimes called the conflict graph of the cycle. A graph with a spanning cycle is planar if and only if it's conflict graph is two-colorable, the colors being "draw inside" and "draw outside". You can read more in the planar graphs chapter in Douglas West's intro to graph theory textbook. $\endgroup$ – Jack M Oct 18 '17 at 10:29
30
$\begingroup$

It's not planar. If you delete the vertex $j$ and the edge $bf,$ what's left is homeomorphic to $K_{3,3}.$

$\endgroup$
  • $\begingroup$ I see it now! Thank you! $\endgroup$ – John21 Oct 17 '17 at 1:51
  • 1
    $\begingroup$ @John21 You can accept the answer you found most helpful (presumably Misha's answer in this case) by clicking on the check mark next to it. $\endgroup$ – bof Oct 17 '17 at 6:17
  • $\begingroup$ Homomorphic. HomEomorphism is something else. Otherwise a nice and simple answer. $\endgroup$ – Heimdall Oct 17 '17 at 11:35
  • 3
    $\begingroup$ @Heimdall Homeomorphic. $\endgroup$ – bof Oct 17 '17 at 11:44
  • $\begingroup$ @bof My mistake. First, I meant isomorphic. Second, it's not isomorphic, it's isomorphic to a subdivision, which, as I've just found out, is called homeomorphic. (I guess because it's the same as topological homeomorphism of graphs considered as subspaces of R^3, for example.) $\endgroup$ – Heimdall Oct 17 '17 at 11:59
5
$\begingroup$

You can use Hopcroft & Tarjan's 1974 "efficient planarity Testing" O(N) algorithm to check for planarity. A detailed explanation can be found in the "Planarity Testing by Path Addition" thesis.

Start by performing a Depth-First search on (each biconnected component of) the graph:

A --> E --> D --> I --> G --> L --> A
                        |      \
                        |       --> C --> B --> D
                        |           |      \
                        |           |       --> F --> I
                        |           |            \
                        |           |             --> A
                        |            \
                        |             --> J --> D
                        |                  \
                        |                   --> E
                         \
                          --> K --> H --> E

Then splitting (each biconnected component of) the graph into a cycle and a hierarchy of chords (each composed of zero-or-more tree/forward edges of the DFS and exactly one co-tree/back edge of the DFS):

A --> E --> D --> I --> G --> L --> A

                              L --> C --> B --> F --> A

                                                F --> I

                                          B --> D

                                    C --> J --> E

                                          J --> D

                        G --> K --> H --> E

The method for picking which edge continues a cycle/chord that is detailed in the linked paper/thesis but it can be (briefly) summarised such that:

  • Each chord will terminate at the lowest reachable ancestor in the DFS tree
  • If multiple chords could reach this ancestor then one where the DFS sub-tree rooted at that vertex can reach only that one lowest ancestor will be preferred over a chord that can only reach multiple lower ancestors. So there are two branching paths of the DFS sub-tree rooted at L that can reach the lowest ancestor A but the path L --> C can reach more than one ancestor of L (the ancestors A, E, D and I) whereas the sub-tree starting with L --> A can only reach A so is the preferred path.
  • If there are still multiple paths with equivalent highest preference then pick any one.

Then, starting with the cycle, successively add each chord to the embedding of the graph in DFS post-order:

So the cycle A --> E --> D --> I --> G --> L --> A is embedded first then is bisected by the chord L -> C --> B --> F --> A and then F --> I on the inside of that cycle:

A --> E --> D --> I --> G --> L
^\                ^           |\
| \            __/            | |
|  \          /               | |
|   \----<-- F <-- B <-- C <-/  |
 \_____________________________/

Then we try to embed B --> D and find that it cannot be embedded as there is no face containing both the vertices B and D and a non-planar minor has been found (in this case, homeomorphic to k(3,3)).

A --> E --> D --> I --> G --> L
^\          ^     ^           |\
| \         |   _/            | |
|  \        |  /              | | 
|   \       \_/__             | |
|    \       /   \            | |
|     \-<-- F <-- B <-- C <--/  |
 \_____________________________/
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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