Shorter Labeling Schemes for Planar Graphs
From MaRDI portal
Publication:5866447
DOI10.1137/20M1330464OpenAlexW4288264622MaRDI QIDQ5866447
Cyril Gavoille, Michał Pilipczuk, Marthe Bonamy
Publication date: 21 September 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1330464
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Asymptotically optimal induced universal graphs
- Graph minors. XX: Wagner's conjecture
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Better distance labeling for unweighted planar graphs
- Induced-universal graphs for graphs with bounded maximum degree
- On induced-universal graphs for the class of bounded-degree graphs
- Interval representations of planar graphs
- Splitting necklaces
- Planar graphs and poset dimension
- Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
- Efficient graph representations
- Sublinear-space distance labeling using hubs
- Small universal graphs for bounded-degree planar graphs
- Notes on graph product structure theory
- An improved planar graph product structure theorem
- Near-optimal induced universal graphs for cycles and paths
- Planar graphs have 1-string representations
- Layered separators in minor-closed graph classes with applications
- Informative labeling schemes for graphs
- Succinct encodings for families of interval graphs
- A fast algorithm for the product structure of planar graphs
- New Routing Techniques and their Applications
- An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets
- Optimal Distance Labeling for Interval Graphs and Related Graph Families
- Universal graphs and induced-universal graphs
- Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
- On Graphs Which Contain All Sparse Graphs
- Implicat Representation of Graphs
- On Triangle Contact Graphs
- Simpler, faster and shorter labels for distances in graphs
- Adjacency Labeling Schemes and Induced-Universal Graphs
- Optimal Induced Universal Graphs and Adjacency Labeling for Trees
- Labeling Schemes for Flow and Connectivity
- Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
- Adjacency Labelling for Planar Graphs (and Beyond)
- Planar graphs have bounded nonrepetitive chromatic number
- Planar Graphs Have Bounded Queue-Number
- Compact and localized distributed data structures
- Shorter Labeling Schemes for Planar Graphs
- Labeling Schemes for Bounded Degree Graphs
- Optimal Distance Labeling Schemes for Trees
- Near-optimal labeling schemes for nearest common ancestors
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Short Labels by Traversal and Jumping
This page was built for publication: Shorter Labeling Schemes for Planar Graphs