###
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.