Halin graph algorithms made simple

I have a new paper on the arXiv, D3-reducible graphs (arXiv:1502.05334), but it's a small one that is not related to this week's many conference submission deadlines (ICALP yesterday, COLT tomorrow, WADS friday). One reason for its existence was that I wanted an implementable algorithm for working with Halin graphs (the graphs that you get by drawing a tree in the plane, with no degree-two vertices, and then connecting the leaves by a cycle surrounding the tree) and the algorithms that I could find for them were based on linear-time planarity testing, something I haven't yet worked up the courage to try implementing. Instead I found that it's possible to recognize Halin graphs, and to solve a wide class of related problems (such as finding their planar embeddings, decomposing them into a tree and a cycle, or finding a Hamiltonian cycle) using a simple reduction-based algorithm that repeatedly finds and simplifies certain local configurations within the graph. The two reductions that I used are shown below; one of them collapses a triangle of degree-three vertices to a point, and the other shortens certain paths of degree-three vertices.

Every Halin graph can be simplified by these reductions to a complete graph on four vertices; in terms of the tree and cycle decomposition of the Halin graph, one of these reductions removes the children from a tree node with two leaf children, and the other removes the middle of three consecutive leaf children. But if you want to use these to recognize Halin graphs only, you need to restrict them a little, because some other graphs can also be simplified to the same four-vertex complete graph, and that's mostly what the paper is about. I call these D3-reducible graphs, and they have a lot of properties in common with the Halin graphs: they are planar, minimally 3-vertex-connected, Hamiltonian, bounded treewidth, etc. One of the smallest examples of a D3-reducible graph that is not a Halin graph is the truncated tetrahedron graph:

I have updated my PADS Python algorithm library to include the new Halin graph recognition algorithm, and some related algorithms, as Halin.py. (I also updated the license text for the library, to use the MIT license — you can do almost anything you want but don't hold me responsible for it — rather than trying to claim that the code is public domain, which I'm told is not so meaningful legally.)

Comments: