Traversal of a quasi-planar subdivision without using mark bits (extended abstract)
Edgar Chávez, Jaroslav Opatrný, Stefan Dobrev, Ladislav Stacho, Evangelos Kranakis, Jorge Urrutia · 2004
Summary form only given. The problem of traversal of planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications. The first such algorithms were able to traverse triangulated subdivisions. Later these algorithms were extended to traverse vertices of an arrangement or a convex polytope. The research progress culminated in an algorithm that can traverse any planar subdivision. We extend the notion of planar subdivision to quasiplanar subdivision in which we allow many edges to cross each other. We describe an algorithm to traverse any quasiplanar subdivision that satisfies a simple requirement. The worst case running time of our algorithm is O(|E| log |E|), which matches the running time of the traversal algorithm for planar subdivisions.