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:
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Aren't there two subgraphs you have to check? $\endgroup$– Sort of DamoclesOct 17, 2017 at 1:26
-
3$\begingroup$ Yes, but it's pretty obvious that it can't contain K5 as a subgraph. $\endgroup$– John21Oct 17, 2017 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$– bofOct 17, 2017 at 6:14
-
$\begingroup$ I'm sure you guys are right, I was truly asking :) $\endgroup$– Sort of DamoclesOct 17, 2017 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 LavrovOct 18, 2017 at 15:31
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
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:
(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:
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.)
answered Oct 17, 2017 at 2:42
-
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$ Oct 17, 2017 at 3:01
-
6$\begingroup$ But checking planarity does not require finding Ham cycle. Planarity is much easier problem. $\endgroup$– rus9384Oct 17, 2017 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$ Oct 17, 2017 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$– MT0Oct 18, 2017 at 10:19
-
3$\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 MOct 18, 2017 at 10:29
$\begingroup$
$\endgroup$
4
It's not planar. If you delete the vertex $j$ and the edge $bf,$ what's left is homomorphic to $K_{3,3}.$
-
-
1$\begingroup$ Homomorphic. HomEomorphism is something else. Otherwise a nice and simple answer. $\endgroup$– HeimdallOct 17, 2017 at 11:35
-
3
-
$\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$– HeimdallOct 17, 2017 at 11:59
$\begingroup$
$\endgroup$
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
Lthat can reach the lowest ancestorAbut the pathL --> Ccan reach more than one ancestor ofL(the ancestorsA,E,DandI) whereas the sub-tree starting withL --> Acan only reachAso 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 <--/ |
\_____________________________/
