Institutional Repository UDD

Fast and Compact Planar Embeddings

Show simple item record

dc.contributor.author Ferres, Leo
dc.contributor.author Fuentes-Sepúlveda, José
dc.contributor.author Gagie, Travis
dc.contributor.author He, Meng
dc.contributor.author Navarro, Gonzalo
dc.date.accessioned 2020-10-30T14:23:05Z
dc.date.available 2020-10-30T14:23:05Z
dc.date.issued 2019
dc.identifier.citation Computational Geometry Volume 89, August 2020 es
dc.identifier.uri https://doi.org/10.1016/j.comgeo.2020.101630 es
dc.identifier.uri http://hdl.handle.net/11447/3506
dc.description.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. es
dc.format.extent 36 p. es
dc.language.iso en es
dc.subject Planar embedding es
dc.subject Compact data structures es
dc.subject Parallel construction es
dc.title Fast and Compact Planar Embeddings es
dc.type Article es


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account