Halin graph

From Wikipedia, the free encyclopedia
A Halin graph.

In graph theory, a Halin graph is a type of planar graph. It is constructed from a tree that has at least four vertices, none of which have exactly two neighbors. The tree is drawn in the plane so none of its edges cross; then edges are added that connect all its leaves into a cycle.[1] Halin graphs are named after German mathematician Rudolf Halin, who studied them in 1971,[2] but the cubic Halin graphs had already been studied over a century earlier by Kirkman.[3]

Construction

A triangular prism, constructed as a Halin graph from a six-vertex tree

A Halin graph is constructed as follows. Let T be a tree with more than three vertices, such that no vertex of T has degree two (that is, no vertex has exactly two neighbors), embedded in the plane. Then a Halin graph is constructed by adding to T a cycle through each of its leaves, such that the augmented graph remains planar.

Examples

Wheel graphs

A star is a tree with exactly one internal vertex. Applying the Halin graph construction to a star produces a wheel graph, the graph of a pyramid. The graph of a triangular prism is also a Halin graph: it can be drawn so that one of its rectangular faces is the exterior cycle, and the remaining edges form a tree with four leaves, two interior vertices, and five edges.

The Frucht graph, one of the two smallest cubic graphs with no nontrivial graph automorphisms, is also a Halin graph.

Properties

Every Halin graph is 3-connected, meaning that it is not possible to delete two vertices from it and disconnect the remaining vertices. It is edge-minimal 3-connected, meaning that if any one of its edges is removed, the remaining graph will no longer be 3-connected.[1] By Steinitz's theorem, as a 3-connected planar graph, it can be represented as the set of vertices and edges of a convex polyhedron; that is, it is a polyhedral graph. And, as with every polyhedral graph, its planar embedding is unique up to the choice of which of its faces is to be the outer face.[1]

Every Halin graph is a Hamiltonian graph, and every edge of the graph belongs to a Hamiltonian cycle. Moreover, any Halin graph remains Hamiltonian after deletion of any vertex.[4] Because every tree without vertices of degree 2 contains two leaves that share the same parent, every Halin graph contains a triangle. In particular, it is not possible for a Halin graph to be a triangle-free graph nor a bipartite graph. More strongly, every Halin graph is almost pancyclic, in the sense that it has cycles of all lengths from 3 to n with the possible exception of a single even length. Moreover, any Halin graph remains almost pancyclic if a single edge is contracted, and every Halin graph without interior vertices of degree three is pancyclic.[5]

Every Halin graph has treewidth at most three.[6] Therefore, many graph optimization problems that are NP-complete for arbitrary planar graphs, such as finding a maximum independent set, may be solved in linear time on Halin graphs using dynamic programming.[7]

The weak dual of an embedded planar graph has vertices corresponding to bounded faces of the planar graph, and edges corresponding to adjacent faces. The weak dual of a Halin graph is always biconnected and outerplanar. This property may be used to characterize the Halin graphs: an embedded planar graph is a Halin graph, with the leaf cycle of the Halin graph as the outer face of the embedding, if and only if its weak dual is biconnected and outerplanar.[8]

History

In 1971, Halin introduced the Halin graphs as a class of minimally 3-vertex-connected graphs: for every edge in the graph, the removal of that edge reduces the connectivity of the graph.[2] These graphs gained in significance with the discovery that many algorithmic problems that were computationally infeasible for arbitrary planar graphs could be solved efficiently on them,[4][8] a fact that was later explained to be a consequence of their low treewidth.[6][7]

Prior to Halin's work on these graphs, graph enumeration problems concerning the cubic Halin graphs were studied in 1856 by Thomas Kirkman[3] and in 1965 by Hans Rademacher.[9] Rademacher calls these graphs based polyhedra. He defines them as the cubic polyhedral graphs with f faces in which one of the faces has f − 1 sides. The graphs that fit this definition are exactly the cubic Halin graphs.

The Halin graphs are sometimes also called roofless polyhedra,[4] but, like "based polyhedra", this name may also refer to the cubic Halin graphs.[10] The convex polyhedra whose graphs are Halin graphs have also been called domes.[11]

References

  1. ↑ 1.0 1.1 1.2 Encyclopaedia of Mathematics, first Supplementary volume, 1988, ISBN 0-7923-4709-9, p. 281, article "Halin Graph", and references therein.
  2. ↑ 2.0 2.1 Halin, R. (1971), "Studies on minimally n-connected graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 129–136, MR 0278980 .
  3. ↑ 3.0 3.1 Kirkman, Th. P. (1856), "On the enumeration of x-edra having triedral summits and an (x − 1)-gonal base", Philosophical Transactions of the Royal Society of London: 399–411, JSTOR 108592 .
  4. ↑ 4.0 4.1 4.2 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 .
  5. ↑ Skowrońska, Mirosława (1985), "The pancyclicity of Halin graphs and their exterior contractions", in Alspach, Brian R.; Godsil, Christopher D., Cycles in Graphs, Annals of Discrete Mathematics 27, Elsevier Science Publishers B.V., pp. 179–194 .
  6. ↑ 6.0 6.1 Bodlaender, Hans (1988), Planar graphs with bounded treewidth, Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University .
  7. ↑ 7.0 7.1 Bodlaender, Hans (1988), "Dynamic programming on graphs with bounded treewidth", Proceedings of the 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 317, Springer-Verlag, pp. 105–118 .
  8. ↑ 8.0 8.1 Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635 .
  9. ↑ Rademacher, Hans (1965), "On the number of certain types of polyhedra", Illinois Journal of Mathematics 9: 361–380, MR 0179682 .
  10. ↑ Lovász, L.; Plummer, M. D. (1974), "On a family of planar bicritical graphs", Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London: Cambridge Univ. Press, pp. 103–107. London Math. Soc. Lecture Note Ser., No. 13, MR 0351915 .
  11. ↑ Demaine, Erik D.; Demaine, Martin L.; Uehara, Ryuhei (2013), "Zipper unfolding of domes and prismoids", Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, pp. 43–48 .

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.