  We describe and implement two local reduction rules that can be used to
recognize Halin graphs in linear time, avoiding the complicated planarity
testing step of previous linear time Halin graph recognition algorithms. The
same two rules can be used as the basis for linear-time algorithms for other
algorithmic problems on Halin graphs, including decomposing these graphs into a
tree and a cycle, finding a Hamiltonian cycle, or constructing a planar
embedding. These reduction rules can also be used to recognize a broader class
of polyhedral graphs. These graphs, which we call the D3-reducible graphs, are
the dual graphs of the polyhedra formed by gluing pyramids together on their
triangular faces; their treewidth is bounded, and they necessarily have
Lombardi drawings.
