Is this graph a planar graph or not?

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:

Solution 1:

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.)

Solution 2:

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

Solution 3:

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 <--/  |
 \_____________________________/