Fast and compact planar embeddings

Abstract

There are many representations of planar graphs but few are as elegant as Turán’s (1984): it is simple and practical, uses only four bits per edge, can handle multi-edges and can store any specified embedding. Its main disadvantage has been that “it does not allow efficient searching” (Jacobson, 1989). In this paper we show how to add a sublinear number of bits to Turán’s representation such that it supports fast navigation, thus overcoming this disadvantage. Other data structures for planar embeddings may be asymptotically faster or smaller but ours is simpler, and that can be a theoretical as well as a practical advantage: e.g., we show how our structure can be built efficiently in parallel.