Fast and Compact Planar Embeddings
Date
2019
Type:
Article
item.page.extent
36 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 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.
Description
item.page.coverage.spatial
item.page.sponsorship
Citation
Computational Geometry Volume 89, August 2020
Keywords
Planar embedding, Compact data structures, Parallel construction