---
abstract: 'We first prove a one-to-one correspondence between finding Hamiltonian cycles in a cubic planar graphs and finding trees with specific properties in dual graphs. Using this information, we construct an exact algorithm for finding Hamiltonian cycles in cubic planar graphs. The worst case time complexity of our algorithm is O$(2^n)$.'
author:
- |
    **Bohao Yao\
    **Charl Ras, Hamid Mokhtar\
    **The University of Melbourne******
title: '**An algorithm for finding Hamiltonian Cycles in Cubic Planar Graphs**'
---

Introduction
============

A [*Hamiltonian cycle*]{} is a cycle which passes through every vertex in a graph exactly once. A [*planar graph*]{} is a graph which can be drawn in the plane such that no edges intersect one another. A [*cubic graph*]{} is a graph in which all vertices have degree 3. Finding a Hamiltonian cycle in a cubic planar graph is proven to be an $\mathcal{NP}$-Complete problem [@garey1976planar]. This implies that unless $\mathcal{P}=\mathcal{NP}$, we could not find an efficient algorithm for this problem. Most approaches to finding a Hamiltonian cycle in planar graph utilises the [*divide-and-conquer*]{} method, or its derivation, the [*separator theorem*]{} which partitions the graph in polynomial time [@lipton1979separator]. Exact algorithms using such methods were found to have the complexity of O$(c^{\sqrt{n}})$ [@klinz2006exact] [@dorn2005efficient], where [*n*]{} denotes the number of vertices and [*c*]{} is a constant. In this paper, we consider only cubic planar graphs and attempt to find a new algorithm to provide researchers with a new method to approaching this problem.

The Expansion Algorithm
=======================

We first start by introducing our so-called [*Expansion Algorithm*]{} which increases the number of vertices in a cycle at each iteration. A cycle can be first found by taking the outer facial cycle of the planar graph. We define it as the [*base cycle*]{}, $\sigma_0$. This base cycle is then expanded by the Expansion Algorithm, which will be described in detail later.

\[def1\] Consider a planar graph $G=(V,E)$

A *complementary path*, $P_e^\sigma$, is a path between 2 adjacent vertices, $v_1, v_2 \in \sigma$ connected by the edge, $e$, s.t. $P_e^\sigma$ is internally disjoint from $\sigma$.

Furthermore, $P_e^\sigma$ and $e$ together will form the boundary of a face in $G$.

Assuming we are not dealing with multigraphs, the complementary path will always have at least one other vertex besides $v_1, v_2$.

The restriction that $P_e^\sigma$ and $e$ have to form the boundary of a face will be used later to prove Corollary \[cor1\].

\[def2\] Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$. Then, $G_1+G_2 := (V_1 \cup V_2,E_1 \cup E_2)$

\[alg1\]

[**Let**]{} $\sigma_0$ be the outer facial cycle.\
[**Let**]{} $i=0$

At each iteration, the algorithm removes an edge, $e$ and adds a path $P_e^\sigma$. Since there are no vertices on $e$ and there is at least 1 vertex on $P_e^\sigma$, the number of vertices on the cycle will always increase at each iteration. Since there is only a finite amount of vertices in the graph, the algorithm will have to terminate eventually.

![Example of utilizing the Expansion Algorithm with the base cycle in blue](Expansion.eps)

The *interior* of a cycle, $C$, is the connected region lying to the left of an anticlockwise orientation of $C$.

\[lem2\] At each iteration of the Algorithm \[alg1\], all the vertices of G either lie in the interior of $\sigma$, or on $\sigma$.

Let $P_i$ be the statement that all the vertices of G either lie in the interior of $\sigma_i$

-   $P_0$ is true as $\sigma_0$ is the outer facial cycle, with all the vertices either lie in the interior or on $\sigma_0$.

-   Assume $P_k$ true. Then all the vertices either lie in the interior or on $\sigma_k$. Assume $\exists P_{e_k}^{\sigma_k}$, then $\sigma_{k+1}$ exists. Let $f_k$ be the face bounded by $P_{e_k}^{\sigma_k}$ and $e_k$. The interior of $f_k$ originally lies inside $\sigma_k$. But by an iteration of Algorithm \[alg1\], the interior of $f_k$ now lies outside the new base cycle, $\sigma_{k+1}$. However, since there are no vertices in the interior of a face, all the vertices in $\sigma_{k+1}$ also lies either in the interior or on $\sigma_{k+1}$. Therefore, if $\sigma_{k+1}$ exists, then $P_k \Rightarrow P_{k+1}$.

Hence, by mathematical induction, $P_i$ is true $\forall i$ as long as $\sigma_i$ exists.

\[cor1\] If $P_e^\sigma$ exists for an edge $e \in \sigma$, then $P_e^\sigma$ is unique.

By Lemma \[lem2\], none of the vertices can lie outside $\sigma$, thus, $P_e^\sigma$ also lies in the interior of $\sigma$. Any edge $e$ lies on the boundary of 2 faces. If $e \in \sigma$, then $\exists$ only 1 possible $P_e^\sigma$ such that $e$ and $P_e$ forms the boundary of a face that lies in the interior of $\sigma$ (the other face that $e$ is a boundary of lies outside $\sigma$)

\[lem1\] If $G$ have a Hamiltonian cycle, then $\exists$ a choice of complementary paths that algorithm \[alg1\] can use to find that Hamiltonian cycle.

Consider a Hamiltonian cycle, $C$, in $G$. If $C = \sigma_0$ then the case is trivial. If $C \ne \sigma_0$, then by Lemma \[lem2\], all vertices in $C$ lies either on or in the interior of $\sigma_0$ since $C$ contains all the vertices of the graph. Since $C$ contains all the vertices and $\sigma_0$ is a cycle and therefore must contain at least 3 vertices, $C \cap \sigma_0 \ne \emptyset$.

Suppose $C \ne \sigma_0$. Let $v_1,v_2,...,v_n$ be consecutive vertices on $\sigma_0$ about the clockwise rotation. Let $P_i$ be the path connecting $v_i,v_{i+1}$ that is the subpath of $C$. Let the edge between $v_i$ and $v_{i+1}$ be $e_i$ which also lies on $\sigma_0$. Since $C$ contains all the vertices in the graph, by iteratively finding $P_e^\sigma$, starting with $e = e_i$, more subpath of $P_i$ will lie on $\sigma$ at each iteration. The algorithm will only move on when $P_i \subset \sigma$.

Repeating this process $\forall i$, we will eventually end up with $\sigma = C$, in which the algorithm will terminate.

![Illustration of the proof for Lemma \[lem1\] with $C$ in red](Graph1.eps)

The Problem in the Dual Graph
=============================

Given a cubic planar graph, $G$, and the corresponding dual graph, $\overline{G}=(\overline{V},\overline{E})$. A *corresponding face*, $f_{\overline{v}} \in G$, is the face corresponding to the vertex $\overline{v} \in \overline{G}$.

The *outer vertex*, $\overline{v}^*$, is the vertex in $\overline{G}$ that corresponds to the outer face of $G$.

Let $e \in G$ be the shared boundary between $f_{\overline{v}_1},f_{\overline{v}_2}$. A *dual edge*, $\overline{e} \in \overline{G}$, is defined as an edge between $\overline{v}_1, \overline{v}_2 \in \overline{G}$.

![Example of $\overline{e}$ and $\overline{v}^*$](v.eps)

Consider Algorithm \[alg1\]. Since $P_e^\sigma$ is unique for an edge $e$ by Corollary \[cor1\], let $e_0,e_1,...,e_n$ be the edges chosen in the [Expansion Algorithm]{} in order. Let $\overline{e}_0,\overline{e}_1,...,\overline{e}_n$ be the corresponding dual edges in $\overline{G}$.

![Expansion Algorithm in the Dual Graph with $\overline{T}$ in Purple](Expansion_Dual.eps)

\[lem3\] $\bigcup\limits_{i=0}^n \overline{e}_i$ is a tree ($\overline{T}$).

Let $P_a$ be the statement that $\bigcup\limits_{i=0}^a \overline{e}_i$ is a tree.

-   $P_0$ is true as 2 vertices connected by an edge, $\overline{e}_0$ is considered a tree.

-   Assume $P_k$ is true. Then $\bigcup\limits_{i=0}^k \overline{e}_i$ is a tree. From proof of Corollary \[cor1\], $e_{k+1}$ is a boundary of 2 faces, one that lies inside $\sigma_{k+1}$ ($f_1$) and another that lies outside $\sigma_{k+1}$ ($f_2$). From proof of Lemma \[lem2\], by including path $P_{e_i}^{\sigma_i}$, the face bounded by $e_i$ and $P_{e_i}^{\sigma_i}$ which originally lies in the interior of $\sigma_i$ will now lie on the exterior of $\sigma_{i+1}$. Therefore, the vertex in $\overline{G}$ that corresponds to $f_1$ will lie outside $\overline{T}$ while the vertex that corresponds to $f_2$ will lie inside $\overline{T}$. Thus, $\overline{e}_{k+1}$ will connect a vertex on $\overline{T}$ to a vertex that is outside of $\overline{T}$, thus expanding the tree. Hence $\bigcup\limits_{i=0}^{k+1} \overline{e}_i$ is also a tree and therefore $P_{k+1}$ is true. Thus, $P_k \Rightarrow P_{k+1}$.

By mathematical induction, $\bigcup\limits_{i=0}^n \overline{e}_i$ is a tree.

From Lemma \[lem2\], we know that faces $f_k$, bounded by $e_k$ and $P_{e_k}^{\sigma_k}$, will be on the exterior of $\sigma$ if $e_k$ was used in the algorithm. Conversely, if $e_k$ was not used in the algorithm, then $f_k$ will be in the interior of the cycle $\sigma$. This is equivalent to stating that all the vertices in $\overline{T}$ lies outside $\sigma$ while all the vertices not in $\overline{T}$ lies in the interior or $\sigma$.

\[lem4\] If $\overline{v} \in \overline{G}$ lies on $\overline{T}$, then all the vertices in $G$ on $f_{\overline{v}}$ lies on $\sigma_n$.

If $\overline{v}$ lies on the tree, then $\exists P_e^\sigma$ s.t. all its vertices in $G$ on $f_{\overline{v}}$ lies on $P_e^\sigma$ since the face is bounded by $P_e^\sigma$ and $e$. Since each iteration of the algorithm will only remove an edge and not any vertices, all the vertices already on the cycle will remain on the cycle at each iteration.

\[thm1\] $G$ has a Hamiltonian cycle if and only if $\exists \overline{T}$ found by Algorithm \[alg1\], with $\overline{v}^*$ at the root, that satisfy the following properties:

1.  For each vertex $v \in G$ that lies on the boundaries of $f_{\overline{v}_1},f_{\overline{v}_2},f_{\overline{v}_3}$, at least one of the vertices, $\overline{v}_1,\overline{v}_2,\overline{v}_3 \in \overline{G}$, lies on $\overline{T}$.

2.  No two vertices on $\overline{T}$ can be joined by an edge $\overline{e}$ unless $\overline{e} \in \overline{T}$.

By first taking the outer facial cycle, $\sigma_0$, only $\overline{v}^*$ lies outside our base cycle. Hence, $\overline{T}$ starts with $\overline{v}^*$ as its root.

($\Rightarrow$) We will begin by proving each of the following property:

1.  If $G$ has a Hamiltonian cycle, then $\exists$ a cycle in $G$ that uses every vertex in $G$. If none of the vertices, $\overline{v}_1,\overline{v}_2,\overline{v}_3$, lies on $\overline{T}$, then none of the $P_e^\sigma$ found by Algorithm \[alg1\] could contain $v$ from negation of Lemma \[lem4\]. This contradicts the definition of a Hamiltonian cycle. Therefore, at least one of the vertices lies on $\overline{T}$.

    ![A vertex lies on the cycle (blue) as $\overline{v}_1 \in \overline{T}$ (purple)](Thm1_1.eps)

2.  If 2 vertices, $\overline{v}'_1, \overline{v}'_2 \in \overline{T}$ are adjacent, $\exists$ 2 vertices shared by $f_{\overline{v}'_1},f_{\overline{v}'_2} \in G$. However, the edge between them is not used on $\overline{T}$. This implies that the 2 vertices will lie on the corresponding path in $G$ twice, once from each face $f_{\overline{v}'_1},f_{\overline{v}'_2} \in G$. This is a contradiction from the definition of a Hamiltonian cycle.

    [.5]{} ![$\overline{v}_1,\overline{v}_2 \in \overline{T}$ and $\overline{e} \in \overline{T}$](Thm1_21.eps "fig:"){width=".4\linewidth"}

    [.5]{} ![$\overline{v}_1,\overline{v}_2 \in \overline{T}$ and $\overline{e} \in \overline{T}$](Thm1_22.eps "fig:"){width=".4\linewidth"}

($\Leftarrow$) Suppose that $\overline{T}=\bigcup\limits_{i=0}^n \overline{e}_i$ is a tree found by Algorithm \[alg1\] that $\overline{T}$ satisfies those properties. From 2, we apply restriction on $\overline{T}$ such that the path in $G$ passes through each vertex at most once (as proven previously). From 1, we know the path passes through every vertex in $G$ at least once. Since there is a path in $G$ that passes through every vertex at most once and at least once, we know the path passes through every vertex in $G$ once. Furthermore, we know that Algorithm \[alg1\] will always output a cycle, $\sigma$. Therefore, we know that $\overline{T}$ satisfying those properties will correspond to a Hamiltonian cycle in $\overline{G}$

Note that Theorem \[thm1\] is a corollary of a theorem by Skupie[ń]{} [@skupien2002hamiltonicity].

Finding $\overline{T}$
======================

We start solving the problem by modifying a backtracking algorithm (**procedure** `solve`) with restrictions (**procedure** `update`) to limit the amount of guessing required. Restrictions from **procedure** `update` may cause the tree to form 2 disjoint graphs, in which case a new backtracking algorithm (**procedure** `disjoint`) is called to trace a path between the graphs. If a particular choice of paths does not work, the algorithm will negate that choice (**procedure** `backtrack`). The algorithm will terminate if it successfully find $\overline{T}$ (all verties assigned) or if all other choices are exhausted, concluding that the graph has no Hamiltonian cycle.

Search Algorithm
----------------

\[alg2\] To find $\overline{T}$ with properties in Theorem \[thm1\], we use a modified backtracking algorithm.

[**procedure**]{} update($\overline{G},\overline{v}$):\

[**procedure**]{} backtrack($\overline{G},\overline{v}$):\
$V(\overline{T}):= V(\overline{T}) - \overline{v}$ $\overline{S}:=\overline{S}+\overline{v}$

[**procedure**]{} solve($\overline{G}$):\

disjoint($\overline{G},\overline{v}$):\

\
$\overline{S} := \emptyset$ $\overline{T} := \left\{\overline{v}^*\right\}$ call solve($\overline{G}$)

Restrictions on vertices does not apply in disjoint graphs where the 2 vertices $\in \overline{T}$ belongs to different sets due to the necessity of connecting the disjoint graphs into one tree.

Complexity
----------

In the worst case scenario, we expect to force at least one vertex into $\overline{S}$ at each guess. This reduces the number of faces in which we have to check to $\frac{f}{2}$ where $f$ is the number of faces in $G$. Since we are working in planar graph, $e=\frac{3}{2}n$ where $n$ is the number of vertices. Using Euler’s formula:

$$\begin{aligned}
n-e+f&=2 \\
n-\frac{3}{2}n+f&=2 \\
f&=2+\frac{n}{2}\end{aligned}$$

Since we have 2 choices ($\overline{T}$ or $\overline{S}$) that we have to guess, in the worst case, our algorithm runs in $2^{\frac{f}{2}}$ or $2^{1+\frac{n}{4}}$. Hence, our algorithm has a time complexity of O$(2^n)$.

Future Research
===============

We could modify Theorem \[thm1\] such that it encompasses any planar graph, $G_2=(V_2,E_2)$ However, caution is advised dealing with faces that share a single vertex, but not a boundary, as this is not reflected in the dual graph, $\overline{G}_2=(\overline{V}_2,\overline{E}_2)$. To overcome this, we introduce the *imaginary edge*.

An *imaginary edge*, $\overline{e}'$ between vertices in $\overline{G}_2$ if the corresponding faces in $G_2$ share a single vertex but not a boundary.

\[thm2\] If $G_2$ has a Hamiltonian cycle then $\exists \overline{T}$ found by Algorithm \[alg1\], with $\overline{v}^*$ at the root, that at least satisfy the following properties:

1.  For each n degree vertex $v \in G_2$ that lies on the boundaries of $f_{\overline{v}_1},f_{\overline{v}_2}, ..., f_{\overline{v}_n}$, at least one of the vertices, $\overline{v}_1,\overline{v}_2, ..., \overline{v}_n \in \overline{G}_2$, lies on $\overline{T}$

2.  No two vertices on $\overline{T}$ can be joined by an edge $\overline{e}$ unless $\overline{e} \in \overline{T}$.

3.  No two vertices joined by an imaginary edge can lie on $\overline{T}$

Properties 1 and 2 are proven in Theorem \[thm1\].

The proof of property 3 follows from the proof of Property 2:

If 2 vertices, $\overline{v}_1, \overline{v}_2 \in \overline{T}$ are joined by an imaginary edge, then the vertex in which $f_{\overline{v}_1}$ and $f_{\overline{v}_2}$ shares will be on the cycle twice. Since this contradicts the definition of a Hamiltonian cycle, property 3 holds.

Acknowledgments
===============

The author wishes to thank his supervisors, Dr Charl Ras and Hamid Mokhtar, for their continued guidance and providing useful insights to this problem.

This paper was supported by the Vacation Research Scholarship awarded by the Australian Mathematical Sciences Institute.

[1]{}

F. Dorn, E. Penninkx, H. L. Bodlaender, and F. V. Foin. Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In [*Algorithms-ESA 2005*]{}, pages 95-106. Springer, 2005.

M. R. Garey, D. S. Johnson, and R. E. Tarjan. The planar hamiltonian circuit problem is NP-complete. [*SIAM Journal of Computing*]{}, 5(4):704-714, 1976.

B. Klinz, G. J. Woeginger, et al. Exact algorithms for the Hamiltonian cycle problem in planar graphs. [*Operations Research Letters*]{}, 34(3):269-274, 2006.

R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. [*SIAM Journal on Applied Mathematics*]{}, 36(2):177-189, 1979.

Z. Skupie[ń]{}. Hamiltonicity of planar cubic multigraphs. [*Discrete mathematics*]{}, 251(1):163-168, 2002.
