The problem of traversal of planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications [7, 8, 11, 13, 12, 17, 18], First such algorithms developed were able to traverse triangulated subdivisions [10], Later these algorithm were extended to traverse vertices of an arrangement or a convex polytope [3]. The research progress culminated to an algorithm that can traverse any planar subdivision [6, 9], In this paper, we extend the notion of planar subdivision to quasi-planar subdivision in which we allow many edges to cross each other. We generalize the algorithm from [9] to traverse any quasi-planar subdivision that satisfies a simple requirement. If we use techniques from [6] the worst case running time of our algorithm will be O(|E| log |E|); which matches with the running time of the traversal algorithm for planar subdivisions [6].

Additional Metadata
Conference Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Citation
Chávez, E., Dobrev, Š., Kranakis, E, Opatrný, J., Stacho, L., & Urrutia, J. (2004). Traversal of a quasi-planar subdivision without using mark bits. Presented at the Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM).