Subhamiltonian graph

In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.[1][2]

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.[2]

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.[3]

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.[4]

History and applications

The class of subhamiltonian graphs (but not this name for them) was introduced by Bernhart & Kainen (1979), who proved that these are exactly the graphs with two-page book embeddings.[5] 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.[2]

Some classes of planar graphs are necessarily Hamiltonian, and therefore also subhamiltonian; these include the 4-connected planar graphs[6] and the Halin graphs.[7]

Every planar graph with maximum degree at most four is subhamiltonian,[4] as is every planar graph with no separating triangles.[8] If the edges of an arbitrary planar graph are subdivided into paths of length two, the resulting subdivided graph is always subhamiltonian.[2]

References
  1. Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 198–218, doi:10.1137/0608018, MR 0881181.
  2. Di Giacomo, Emilio; Liotta, Giuseppe (2010), "The Hamiltonian augmentation problem and its applications to graph drawing", WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010, Proceedings, Lecture Notes in Computer Science, 5942, Berlin: Springer, pp. 35–46, doi:10.1007/978-3-642-11440-3_4, MR 2749626.
  3. For instance in a 2003 technical report "Book embeddings of graphs and a theorem of Whitney", Paul Kainen defines subhamiltonian graphs to be subgraphs of planar Hamiltonian graphs, without restriction on the vertex set of the augmentation, but writes that "in the definition of subhamiltonian graph, one can require that the extension only involve the inclusion of new edges."
  4. Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), "Two-page book embeddings of 4-planar graphs", STACS, arXiv:1401.0684, Bibcode:2014arXiv1401.0684B.
  5. Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2.
  6. Nishizeki, Takao; Chiba, Norishige (2008), "Chapter 10. Hamiltonian Cycles", Planar Graphs: Theory and Algorithms, Dover Books on Mathematics, Courier Dover Publications, pp. 171–184, ISBN 9780486466712.
  7. Cornuéjols, G.; Naddef, D.; Pulleyblank, W. R. (1983), "Halin graphs and the travelling salesman problem", Mathematical Programming, 26 (3): 287–294, doi:10.1007/BF02591867.
  8. Kainen, Paul C.; Overbay, Shannon (2007), "Extension of a theorem of Whitney", Applied Mathematics Letters, 20 (7): 835–837, doi:10.1016/j.aml.2006.08.019, MR 2314718.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.