Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00395
Simple Recognition of Halin Graphs and Their Generalizations
Vol. 20, no. 2, pp. 323-346, 2016. Regular paper.
Abstract 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.
Submitted: November 2015.
Reviewed: April 2016.
Revised: May 2016.
Accepted: May 2016.
Final: June 2016.
Published: June 2016.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX