Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00268
Subgraph Homeomorphism via the Edge Addition Planarity Algorithm
Vol. 16, no. 2, pp. 381-410, 2012. Regular paper.
Abstract This paper extends the edge addition planarity algorithm from Boyer and Myrvold to provide a new way of solving the subgraph homeomorphism problem for K2,3, K4, and K3,3. These extensions derive much of their behavior and correctness from the edge addition planarity algorithm, providing an alternative perspective on these subgraph homeomorphism problems based on affinity with planarity rather than triconnectivity. Reference implementations of these algorithms have been made available in an open source project (http://code.google.com/p/planarity).
Submitted: November 2010.
Reviewed: June 2011.
Revised: July 2011.
Reviewed: March 2012.
Revised: April 2012.
Accepted: July 2012.
Final: July 2012.
Published: August 2012.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX