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 $\ll$ m. This is the first linear-work and practical
parallel algorithm that can encode an embedding of a connected planar graph
compactly.