Shorter Labeling Schemes for Planar Graphs
From MaRDI portal
Publication:5866447
DOI10.1137/20M1330464OpenAlexW4288264622MaRDI QIDQ5866447FDOQ5866447
Authors: Marthe Bonamy, Cyril Gavoille, Michał Pilipczuk 
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
Recommendations
- Shorter Labeling Schemes for Planar Graphs
- Adjacency Labelling for Planar Graphs (and Beyond)
- Shortcutting Planar Digraphs
- Short encodings of planar graphs and maps
- Distance constrained labelings of planar graphs with no short cycles
- The \(L(2,1)\)-labeling on planar graphs
- Labelings of two classes of plane graphs
- Labeling of planar graphs with a condition on distance two
- Labeling schemes for bounded degree graphs
- Simpler, faster and shorter labels for distances in graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XX: Wagner's conjecture
- Planar graphs and poset dimension
- Efficient graph representations
- Labeling Schemes for Flow and Connectivity
- Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
- Interval representations of planar graphs
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Optimal Distance Labeling for Interval Graphs and Related Graph Families
- Implicat Representation of Graphs
- Universal graphs and induced-universal graphs
- On Graphs Which Contain All Sparse Graphs
- On Triangle Contact Graphs
- Informative labeling schemes for graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Splitting necklaces
- Succinct encodings for families of interval graphs
- Title not available (Why is that?)
- Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
- Layered separators in minor-closed graph classes with applications
- Optimal induced universal graphs and adjacency labeling for trees
- Asymptotically optimal induced universal graphs
- Induced-universal graphs for graphs with bounded maximum degree
- On induced-universal graphs for the class of bounded-degree graphs
- Planar graphs have bounded nonrepetitive chromatic number
- Title not available (Why is that?)
- Sublinear-space distance labeling using hubs
- Simpler, faster and shorter labels for distances in graphs
- Shorter Labeling Schemes for Planar Graphs
- Optimal distance labeling schemes for trees
- Better distance labeling for unweighted planar graphs
- Small universal graphs for bounded-degree planar graphs
- Near-optimal induced universal graphs for cycles and paths
- An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets
- Compact and localized distributed data structures
- Notes on graph product structure theory
- New routing techniques and their applications
- Labeling schemes for bounded degree graphs
- A fast algorithm for the product structure of planar graphs
- Planar graphs have bounded queue-number
- Adjacency Labelling for Planar Graphs (and Beyond)
- An improved planar graph product structure theorem
- Planar graphs have 1-string representations
- Forbidden-set distance labels for graphs of bounded doubling dimension
- Near-optimal labeling schemes for nearest common ancestors
- Adjacency labeling schemes and induced-universal graphs
- Short Labels by Traversal and Jumping
Cited In (8)
- Optimal adjacency labels for subgraphs of Cartesian products
- Short Labels by Traversal and Jumping
- Small but unwieldy: a lower bound on adjacency labels for small classes
- Adjacency Labelling for Planar Graphs (and Beyond)
- Product structure of graphs with an excluded minor
- Graph product structure for \(h\)-framed graphs
- Shortcutting Planar Digraphs
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
This page was built for publication: Shorter Labeling Schemes for Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5866447)
