In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar

Hamiltonian graph In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

Definition

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''. It would be equivalent to define ''G'' to be subhamiltonian if ''G'' is a subgraph of a Hamiltonian planar graph, without requiring this larger graph to have the same vertex set. That is, for this alternative definition, it should be possible to add both vertices and edges to ''G'' to create a Hamiltonian cycle. However, if a graph can be made Hamiltonian by the addition of vertices and edges it can also be made Hamiltonian by the addition of edges alone, so this extra freedom does not change the definition. 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 set In graph drawing, a universal point set of order ''n'' is a set ''S'' of points in the Euclidean plane with the property that every ''n''-vertex planar graph has a Fáry's theorem, straight-line drawing in which the vertices are all placed at poin ...

s, 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. and the

Halin graph In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of ...

s. Every planar graph with

maximum degree This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

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

{{reflist, 30em Graph families Planar graphs Hamiltonian paths and cycles