# 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 Halin graph is constructed as follows. Let be a tree with more than three vertices, such that no vertex of has degree two (that is, no vertex has exactly two neighbors), embedded in the plane. Then a Halin graph is constructed by adding to 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.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.0}^{2.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑
^{3.0}^{3.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑
^{4.0}^{4.1}^{4.2}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑
^{6.0}^{6.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑
^{7.0}^{7.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑
^{8.0}^{8.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.

## External links

- Halin graphs, Information System on Graph Class Inclusions.
- Weisstein, Eric W., "Halin Graph",
*MathWorld*.