Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs

DOI10.1007/978-3-540-75520-3_52MaRDI QIDQ3527249zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(22)

• The space complexity of sum labelling
• An adjacency labeling scheme based on a decomposition of trees into caterpillars
• Near-optimal induced universal graphs for cycles and paths
• Compact representation of graphs with bounded bandwidth or treedepth
• Compact navigation and distance oracles for graphs with small treewidth
• Implicat Representation of Graphs
• scientific article; zbMATH DE number 1262796 (Why is no real title available?)
• Adjacency labeling schemes and induced-universal graphs
• Optimal induced universal graphs for bounded-degree graphs
• Induced universal hypergraphs
• Compact navigation and distance oracles for graphs with small treewidth
• Implicit representations and factorial properties of graphs
• Isometric universal graphs
• Twin-width II: small classes
• Asymptotically optimal induced universal graphs
• Shorter Labeling Schemes for Planar Graphs
• Short Labels by Traversal and Jumping
• The space complexity of sum labelling
• Implicit representation of relations
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Tight bounds on adjacency labels for monotone graph classes
• Optimal distance labeling for permutation 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)