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.
Every planar graph with maximum vertex degree is subhamiltonian (Bekos et
al. 2014). More generally, every polyhedral graph
is subhamiltonian (although not necessarily Hamiltonian),
a result which follows from classical results on planar embeddings due to Barnette
and Grünbaum (1969).
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.
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 subhamiltonian (Bekos et
al. 2014). More generally, every polyhedral graph
is subhamiltonian (although not necessarily Hamiltonian),
a result which follows from classical results on planar embeddings due to Barnette
and Grünbaum (1969).
