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.date.accessioned | 2022-03-02T14:38:02Z | |
| dc.date.available | 2022-03-02T14:38:02Z | |
| dc.date.issued | 2017 | |
| dc.description | Conference paper | es |
| dc.description.abstract | There are many representations of planar graphs, but few are as elegant as Turan'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 Turan'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. (C) 2020 Elsevier B.V. All rights reserved | es |
| dc.description.version | VersiĂłn enviada | es |
| dc.identifier.citation | Ferres L., Fuentes J., Gagie T., He M., Navarro G. (2017) Fast and Compact Planar Embeddings. In: Ellen F., Kolokolova A., Sack JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science, vol 10389. Springer, Cham | es |
| dc.identifier.uri | https://doi.org/10.1007/978-3-319-62127-2_33 | es |
| dc.identifier.uri | http://hdl.handle.net/11447/5637 | |
| 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 | Other | es |
| dcterms.source | Lecture Notes in Computer Science | es |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Fast And Compact Planar Embeddings.pdf
- Size:
- 249.63 KB
- Format:
- Adobe Portable Document Format
- Description:
- Texto completo
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: