Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs

DOI10.1007/978-3-540-75520-3_52zbMATH Open1151.68565OpenAlexW1597567432MaRDI QIDQ3527249FDOQ3527249

Authors: Cyril Gavoille, Arnaud Labourel 

Publication date: 25 September 2008

Published in: Algorithms – ESA 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-75520-3_52

Recommendations

• Implicat Representation of Graphs
• Short Labels by Traversal and Jumping
• Implicit representations and factorial properties of graphs
• scientific article; zbMATH DE number 1262796
• On the succinct representation of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Cited In (19)

• Short Labels by Traversal and Jumping
• Isometric universal graphs
• Adjacency labeling schemes and induced-universal graphs
• Implicat Representation of Graphs
• The space complexity of sum labelling
• Induced universal hypergraphs
• Implicit representation of relations
• Near-optimal induced universal graphs for cycles and paths
• Shorter Labeling Schemes for Planar Graphs
• Compact navigation and distance oracles for graphs with small treewidth
• Implicit representations and factorial properties of graphs
• Small but unwieldy: a lower bound on adjacency labels for small classes
• An adjacency labeling scheme based on a decomposition of trees into caterpillars
• Twin-width II: small classes
• The space complexity of sum labelling
• Compact representation of graphs with bounded bandwidth or treedepth
• Compact navigation and distance oracles for graphs with small treewidth
• Optimal induced universal graphs for bounded-degree graphs
• Asymptotically optimal induced universal graphs

This page was built for publication: Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3527249)