# Halin graph

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 at least 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

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. ^ a b c Encyclopaedia of Mathematics, first Supplementary volume, 1988, ISBN 0-7923-4709-9, p. 281, article "Halin Graph", and references therein.
2. ^ a b 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. ^ a b 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. ^ a b c 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. ^ a b Bodlaender, Hans (1988), Planar graphs with bounded treewidth, Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University.
7. ^ a b 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. ^ a b 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.