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.