Subgraph Homeomorphism via the Edge Addition Planarity Algorithm

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 K_2,3, K₄, and K_3,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).