Fast and compact planar embeddings
From MaRDI portal
Publication:5918983
DOI10.1016/j.comgeo.2020.101630zbMath1476.68205arXiv1610.00130OpenAlexW2528068670MaRDI QIDQ5918983
Meng He, Gonzalo Navarro, José Fuentes-Sepúlveda, Travis Gagie, Leo Ferres, José Fuentes
Publication date: 23 October 2020
Published in: Lecture Notes in Computer Science, Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.00130
Related Items
Succinct encoding of binary strings representing triangulations ⋮ Compact representations of spatial hierarchical structures with support for topological queries ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Unnamed Item ⋮ Fast and compact planar embeddings ⋮ Navigating planar topologies in near-optimal space and time
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A compact encoding of plane triangulations with efficient query supports
- On the succinct representation of graphs
- A simple optimal representation for balanced parentheses
- A simple storage scheme for strings achieving entropy bounds
- Succinct representations of planar maps
- A linear-processor algorithm for depth-first search in planar graphs
- Embedding planar graphs in four pages
- Graph compression by BFS
- Short encodings of planar graphs and maps
- An optimal parallel algorithm for planar cycle separators
- Parallel lightweight wavelet tree, suffix array and FM-index construction
- Parallel construction of succinct trees
- Succinct representation of labeled graphs
- The absence of efficient dual pairs of spanning trees in planar graphs
- Planar graphs, via well-orderly maps and trees
- Spanning trees of dual graphs
- A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
- GLOUDS: representing tree-like graphs
- Succinct Representation of Balanced Parentheses and Static Trees
- Fully Functional Static and Dynamic Succinct Trees
- Scheduling multithreaded computations by work stealing
- Planar Depth-First Search in $O(\log n)$ Parallel Time
- Succinct Representations of Separable Graphs
- Parallel Merge Sort
- Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- A Separator Theorem for Planar Graphs
- Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs
- A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
- Array-based Compact Data Structures for Triangulations: Practical Solutions with Theoretical Guarantees
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
- Practical Entropy-Compressed Rank/Select Dictionary
- Orderly Spanning Trees with Applications
- On the Diameter of Random Planar Graphs
- Algorithms and Data Structures
- A Census of Planar Maps
- Fast and compact planar embeddings
- Prefix computations on symmetric multiprocessors
This page was built for publication: Fast and compact planar embeddings
