A graph is subhamiltonian if can be extended by adding edges inside faces of that embedding to a planarHamiltonian
graph. Since the augmented graph is required to be planar,
the original subhamiltonian graph must necessarily be planar.
Subhamiltonian graphs are generally assumed to be connected.
Adopting the convention that the singleton graph is considered connected
and HamiltonianHamiltonian Graph, it is also subhamiltonian.
Every planar graph with maximum vertex degree is subhamiltonian (Bekos et
al. 2014).
Classes for which all members are planar and Hamiltonian are subhamiltonian, including 4-connected planar graphs (Nishizeki and Chiba 2008),
Halin graphs (Cornuéjols et al. 1983),
and triangular grid graphs. Series-parallel
graphs and outerplanar graphs (including trees) are also subhamiltonian.
Every polyhedral graph is also subhamiltonian (although not necessarily Hamiltonian), a result
which follows from classical results on planar embeddings due to Barnette and Grünbaum
(1969).
Barnette, D. W. and GrŸnbaum, B. "On SteinitzÕs Theorem Concerning Convex 3-Polytopes and on Some Properties of Planar Graphs."
In The Many Facets of Graph Theory (Ed. G. Chartrand and S. F, Kapoor).
Berlin: Springer-Verlag, pp. 27-40, 1969.Bernhart, F. R.;
Kainen, P. C. "The Book Thickness of a Graph." J. Combin. Th.,
Ser. B27, 320-331, 1979.Bekos, M. A.; Gronemann, M.;
and Raftopoulou, C. N. "Two-Page Book Embeddings of 4-Planar Graphs."
STACS 2014. https://arxiv.org/abs/1401.0684.Di
Giacomo, E. and Liotta, G. "The Hamiltonian Augmentation Problem and Its Applications
to Graph Drawing." In WALCOM: Algorithms and Computation, 4th International
Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Berlin: Springer,
pp. 35-46, 2010.Cornuéjols, G.; Naddef, D.; and Pulleyblank,
W. R. "Halin Graphs and the Travelling Salesman Problem." Math.
Programming26, 287-294, 1983.Heath, L. S. "Embedding
Outerplanar Graphs in Small Books." SIAM J. Alg. Disc. Meth.8,
198-218, 1987.Nishizeki, T. and Chiba, N. "Hamiltonian Cycles."
Ch. 10 in Planar
Graphs: Theory and Algorithms. New York: Dover, pp. 171-184, 2008.
is considered connected
and HamiltonianHamiltonian Graph, it is also subhamiltonian.
is subhamiltonian (Bekos et
al. 2014).
