Bijective comparison of optimal planarity algorithms
Laura A. Bloom · Linear and Multilinear Algebra · 1995
The Hopcroft-Tarjan and Lempel-Even-Cederbaum algorithms have generally been viewed as different approaches to planarity testing and graph embedding. Canfield and Williamson proved that, with slight modification to the Hopcroft-Tarjan algorithm, these two algorithms can be structured in such a way that they are indistinguishabel on all planar graphs in terms of the order in which the vertices are processed the situation in the case of nonplanar graphs is not discussed by Canfield and Williamson and is, in fact, much more complex. We extend the bijective techniques for comparing these two algorithms to the nonplanar case. Based on a classification scheme for the Structure of overlap graphs, we precisely characterize when one of these algorithms performs better than the other.