Fast and compact planar embeddings
Date
2020
Type:
Article
item.page.extent
21 p.
item.page.accessRights
item.contributor.advisor
ORCID:
Journal Title
Journal ISSN
Volume Title
Publisher
item.page.isbn
item.page.issn
item.page.issne
item.page.doiurl
item.page.other
item.page.references
Abstract
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 multiedges, 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.
Description
item.page.coverage.spatial
item.page.sponsorship
Citation
Computational Geometry 89(2020)
Keywords
Planar embedding, Compact data structures, Parallel construction