Fast and Compact Planar Embeddings
| 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.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.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.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 |