I/O-efficient path traversal in succinct planar graphs

DOI10.1007/s00453-015-0086-7zbMath1364.68305OpenAlexW2281191978MaRDI QIDQ521807

Meng He, Norbert Zeh, Anil Maheshwari, Craig Dillabaugh

Publication date: 12 April 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0086-7

zbMATH Keywords

planar graphsexternal memory algorithmssuccinct data structurespath traversal

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct representations of planar maps
• Finding small simple cycle separators for 2-connected planar graphs
• The book thickness of a graph
• Planar graph blocking for external searching
• Blocking for external graph searching
• Succinct and I/O efficient data structures for traversal in trees
• Succinct geometric indexes supporting point location queries
• Succinct Representations of Arbitrary Graphs
• Succinct and I/O Efficient Data Structures for Traversal in Trees
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Optimal Search in Planar Subdivisions
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Orderly Spanning Trees with Applications
• Succinct Representation of Labeled Graphs
• Algorithms and Data Structures
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• I/O-efficient point location using persistent B-trees