Succinct representation of labeled graphs

DOI10.1007/S00453-010-9452-7MaRDI QIDQ2428673zbMATH OpenOpenAlexFDO

Authors Jérémy Barbay, Luca Castelli Aleardi, Meng He, J. Ian Munro

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-00712915/file/SuccinctLabeledGraphs_Algorithmica_Hal.pdf

zbMATH Keywords

graphdata structuresplanar graphsuccinct data structuresbook embeddingplanar triangulation\(k\)-page graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Succinct Representation of Labeled Graphs
• Succinct representation of labeled trees
• On the succinct representation of graphs
• Succinct representations of separable graphs
• Succinct Representations of Arbitrary Graphs

Cites work

• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 4043769 (Why is no real title available?)
• scientific article; zbMATH DE number 2038722 (Why is no real title available?)
• scientific article; zbMATH DE number 2079399 (Why is no real title available?)
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• A Separator Theorem for Planar Graphs
• Algorithms and Data Structures
• Automata, Languages and Programming
• Balanced parentheses strike back
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar graphs in four pages
• Orderly Spanning Trees with Applications
• Representing trees of higher degree
• Sorting Using Networks of Queues and Stacks
• Succinct Ordinal Trees Based on Tree Covering
• Succinct Representation of Labeled Graphs
• Succinct Representations of Arbitrary Graphs
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct indexes for strings, binary relations and multi-labeled trees
• Succinct representation of balanced parentheses and static trees
• Succinct representations of planar maps
• The book thickness of a graph
• Ultra-succinct representation of ordered trees

Cited in

(20)

• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• A note on succinct representations of graphs
• On the succinct representation of equivalence classes
• Succinct data structures for representing equivalence classes
• Compact representation of graphs of small clique-width
• Succinct representations of separable graphs
• Space-efficient vertex separators for treewidth
• On the succinct representation of graphs
• Succinct data structure for path graphs
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• scientific article; zbMATH DE number 2079399 (Why is no real title available?)
• Compact binary relation representations with rich functionality
• Compact navigation and distance oracles for graphs with small treewidth
• Succinct and Implicit Data Structures for Computational Geometry
• A succinct data structure for self-indexing ternary relations
• Succinct data structures for families of interval graphs
• Succinct Representation of Labeled Graphs
• Navigating planar topologies in near-optimal space and time
• Dynamic compact planar embeddings
• Space efficient data structures for dynamic orthogonal range counting

This page was built for publication: Succinct representation of labeled graphs

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