Fast and Compact Planar Embeddings

Leo Ferres, José Fuentes, Travis Gagie, Meng He, and Gonzalo Navarro

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 first show how to add a sublinear number of bits to Turán's representation such that it supports fast navigation, and then give a linear-work parallel construction algorithm for the resulting data structure that runs in O(m/p) expected time, where m is the number of edges, p is the number of processors and p << m. This is the first linear-work and practical parallel algorithm that can encode an embedding of a connected planar graph compactly.