Subhamiltonian graph

A graph G is subhamiltonian if G is a subgraph of another graph aug(G) on the same vertex set, such that aug(G) is planar and contains a Hamiltonian cycle. For this to be true, G itself must be planar, and additionally it must be possible to add edges to G, preserving planarity, in order to create a cycle in the augmented graph that passes through each vertex exactly once. The graph aug(G) is called a Hamiltonian augmentation of G. In a subhamiltonian graph, a subhamiltonian cycle is a cyclic sequence of vertices such that adding an edge between each consecutive pair of vertices in the sequence preserves the planarity of the graph. A graph is subhamiltonian if and only if it has a subhamiltonian cycle. ==History and applications==

The class of subhamiltonian graphs (but not this name for them) was introduced by , who proved that these are exactly the graphs with two-page book embeddings. Subhamiltonian graphs and Hamiltonian augmentations have also been applied in graph drawing to problems involving embedding graphs onto universal point sets, simultaneous embedding of multiple graphs, and layered graph drawing. ==Related graph classes==

Some classes of planar graphs are necessarily Hamiltonian, and therefore also subhamiltonian. These include the 4-connected planar graphs, by Tutte's theorem on Hamiltonian cycles, and the Halin graphs. Every planar graph with maximum degree at most four is subhamiltonian, as is every planar graph with no separating triangles. If the edges of an arbitrary planar graph are subdivided into paths of length two, the resulting subdivided graph is always subhamiltonian. ==References==