Fast and Compact Planar Embeddings
Leo Ferres, José Fuentes-Sepúlveda, 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 4 bits per edge,
can handle self-loops and 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 while retaining
simplicity.
As a consequence of the inherited simplicity, we offer the first efficient
parallel construction of a compact encoding of
a planar graph embedding. Our experimental results show that the resulting
representation uses about 6 bits per edge in practice, supports basic
navigation operations within a few microseconds, and can be built sequentially
at a rate below 1 microsecond per edge, featuring a linear speedup with a
parallel efficiency around 50% for large datasets.