Hamiltonian Path in 2-Trees.
P. Renjith, N. Sadagopan · arXiv (Cornell University) · 2015
For a graph, a spanning path is a path containing all vertices and it is also known as \emph{Hamiltonian path}. For general graphs, there is no known necessary and sufficient condition for the existence of Hamiltonian path and the complexity of finding a Hamiltonian path in general graphs is NP-Complete. We present a necessary and sufficient condition for the existence of Hamiltonian path in 2-trees. Using our characterization, we also present a polynomial-time algorithm for the existence of Hamiltonian path in 2-trees. We also highlight the fact that 2-trees are well-known subclass of chordal and planar graphs. This paper makes the first attempt in identifying a non-trivial subclass of planar graphs where Hamiltonian path is polynomial-time solvable which is otherwise NP-Complete on planar as well as chordal graphs. Our characterization is based on a deep understanding of the structure of 2-trees and we believe that the combinatorics presented here can be used in other combinatorial problems restricted to 2-trees.