Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section4.2The planarity algorithm for Hamiltonian graphs

In the previous chapter we showed that \(K_{3,3}\) isn't planar; in this section we investigate how the ideas we used to solve the utilities problem for \(K_{3,3}\)-- namely, the Jordan Curve theorem and the fact that \(K_{3,3}\) is Hamiltonian -- generalize to other graphs. In the end, this will culminate in "The Planarity Algorithm for Hamiltonian Graphs".

Subsection4.2.1Stereographic Projection and Unnecessary cases

It will make our life easier if before we investigate other graphs we streamline our proof for \(K_{3,3}\) slightly: there were a few times where we had to treat different cases that wound up behaving essentially the same, and we'd like to see that we didn't actually need to treat them as separate cases. In particular, we would like to show that the following three seemingly different ways to connect the first two vertices lead to the same analysis:

  1. Connecting them inside the Hamiltonian cycle
  2. Connecting them outside "to the left"
  3. Connecting them outside "to the right"
Figure4.2.1The three cases

The solution will be to think about drawing the graphs on the sphere \(S^2\) instead of the plane. First, let's see why this solves our problem. On the plane, the inside of a circle is different from the outside of a circle -- the inside is bounded, but the outside is unbounded. However, on the sphere, the two sides of a circle are equivalent -- you can deform any circle to be an equator, and then the northern hemisphere is equivalent to the southern hemisphere. This shows on there sphere, the inside and the outside aren't really different cases.

Furthermore, going around the outside to "the left" or "to the right" are equivalent on the sphere -- you can slowly make the path around the sphere bigger and bigger, and then slip it around the north or south pole, and back. Alternatively, we've already seen that the inside of the circle is equivalent to the outside of the circle on the sphere \(S^2\text{,}\) and on the inside of the circle it doesn't matter exactly how the two points are connected, and so it shouldn't matter on the outside, either.

So we've argued that if we're trying to draw a graph on the sphere, all three cases are the same, but it should still feel like a bait-and-switch: we weren't trying to draw graphs on there sphere, we were trying to draw graphs on the plane. The connection comes from the fact that the sphere can be viewed as a plane with one additional point.

One way to visualize this is imagine the sphere as being made from very flexible clay. If we poke a small hole in the top of the sphere, we could stick our fingers in and make the hole larger, and gradually stretch and bend and reform for the sphere to be a flat disk.

Alternatively, one could use stereographic projection, as shown in Figure . Draw \(S^2\) in \(\R^3\) as the unit sphere at the origin, and let \(N=(0,0,1)\) be the north pole of the sphere. Stereographic projection gives a bijection between \(S^2\setminus\{N\}\) (the sphere minus the north pole) to the plane, as follows: for any point \(p\neq N\) the line through \(p\) and \(N\) must meet the \(xy\)-plane at one point. On the other hand, any line through \(N\) and a point on the \(xy\)-plane must meet the sphere at one other point.

Accepting that \(S^2\) is \(\reals^2\) minus one point, we see that we can draw a given graph \(G\) on \(S^\) if and only if we can draw \(G\) on \(\reals^2\text{:}\) if we draw it on \(\reals^2\text{,}\) we can view the \(\reals^2\) as a small patch of \(S^2\text{.}\) And if we have a drawing on \(S^2\text{,}\) there must be at least one point on \(S^2\) that isn't in the drawing of \(G\text{,}\) and doing stereographic projection from that point gives a drawing of \(G\) on the plane \(\reals^2\text{.}\)

Subsection4.2.2The planarity algorith

The preceeding discussion may have felt heavy going, but the upshot is that the cases that seemed "the same" in our analysis of \(K_{3,3}\) actually are the same, and similar cases will be the same for any graph. This will make it much easier to extend our reasoning to more complicated graphs.

Suppose that \(G\) is Hamiltonian, and choose a Hamiltonian cycle; if \(G\) were planar than this cycle must be drawn as a circle, and every other edge must either lie entirely inside or entirely outside the graph. Now consider two edges \(e=ab\) and \(f=xy\) that are not part of the cycle. Depending on the order that \(a,b,x\) and \(y\) appear as you go around the Hamiltonian cycle, one of two things will happen:

  1. If the vertices of \(e\) and \(f\) do not interlace (e.g. \(abxy, yxab, xbay,\cdots\)), or if they share a vertex (e.g., \(a=x\)), then \(e\) may be drawn both inside or both outside the circle without crossing
  2. If the vertices of \(e\) and \(f\) do interlace (e.g. \(axby, xayb, yaxb,\dots...\)) then if \(e\) and \(f\) are drawn both inside or both outside the circle, they must cross

This motivates the following definition

Definition4.2.3Cross(\(G,C\))

Let \(G\) be a Hamiltonian graph, and \(C\) a Hamiltonian cycle in \(G\text{.}\) The crossing graph of \(G\) and \(C\text{,}\) denoted Cross(\(G,C\)) has as vertices the edges of \(G\) that aren't in the cycle, and an edge between vertices \(p\) and \(q\) if the vertices of the corresponding edges interleave -- that is, \(p\) and \(q\) are adjacent if they cannot be drawn on the same side of the cycle \(C\) without crossing.

The idea is that if \(G\) is planar, the vertices of Cross(\(G,C\)) are naturally bicolored, with the red vertices, say, corresponding to the edges that are drawn inside the cycle \(C\text{,}\) and the blue edge corresponding to the edges that are drawn outside the cycle \(C\text{.}\) The definition of the edges of Cross(\(G,C\)) guarantees there are no edges between vertices of the same color.

Similarly, if we can find a colouring of the vertices of Cross(\(G,C\)) so that adjacent vertices have different colours, then we can draw all the edges of \(G\) corresponding to red vertices of Cross(\(G,C\)) inside (or outside) \(C\) without having any of them cross.

Let's apply the planarity algorithm to the complete graph \(K_5\text{.}\) Let's label the vertices 1-5, and take our Hamiltonian cycle \(C\) to be 123451, which we've drawn as the outside pentagon in the following figure:

Figure4.2.6The graph (\(K_5\))
Since \(K_5\) has \(\binom{5}{2}=10\) vertices, there are 5 edges that aren't used in \(C\text{,}\) namely 13,14, 24,25, and 35. So Cross(\(K_5, 123451\)) will consist of these five vertices. We see that 13 will be adjacent to 24 and 25, since these edges would cross if drawn inside, but 13 is not adjacent to 14 or 35, since these edges would cross 13 if drawn on the same side of the circle, as illustrated in the next figure

Figure4.2.7The edges 13 does and does not cross

Similar consideration with the other edges show that Cross(\(K_5, 123451\)) is the following graph, which is isomorphic to a five cycle:

Figure4.2.8The graph Cross(\(K_5, 123451\))

In particular, Cross(\(K_5, 123451\)) is not bipartite. Hence, by the planarity algorithm for Hamiltonian graphs, we see that \(K_5\) is not planar.

Let's use the planarity algorithm for Hamiltonian graphs to find a planar drawing of the graph shown in the next figure.

Figure4.2.10A graph \(H\)

We see that \(H\) is Hamiltonian and take as our Hamiltonian cycle the path around the outside, namely \(abcxyza\text{.}\) There are then six edges not contained in the Hamiltonian cycle, and we find that Cross(\(H, abcxyz\)) is as follows:

Figure4.2.11The graph Cross(\(H, abcxyza)\)

For instance, in \(H\) the edge \(ax\) crosses the three edges \(cy, cz\) and \(bz\text{,}\) and so in Cross(\(H, abcxyza\)), the vertex \(ax\) is adjacent to these vertices.

The graph Cross(\(H, abcxyza)\) has no odd cycles and hence is bipartite -- for instance, we may color \(ax, bx\) and \(ay\) red, and the other three vertices blue. Then, to draw \(H\) in the plane without edges crossing, we draw the red edges inside the cycle, and the blue edges outside the cycle:

Figure4.2.12The graph \(H\) drawn without edges crossing