I/O-efficient path traversal in succinct planar graphs

DOI10.1007/S00453-015-0086-7MaRDI QIDQ521807zbMATHOpenAlexFDO

Authors Craig Dillabaugh, Meng He, Anil Maheshwari, Norbert Zeh

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 graphssuccinct data structuresexternal memory algorithmspath traversal

Mathematics Subject Classification ID

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

Recommendations

• I/O and space-efficient path traversal in planar graphs
• I/O-efficient algorithms on near-planar graphs
• I/O-Efficient Algorithms on Near-Planar Graphs
• I/O-efficient undirected shortest paths
• scientific article; zbMATH DE number 2119685
• I/O-Optimal Algorithms for Outerplanar Graphs
• Short path queries in planar graphs in constant time
• scientific article; zbMATH DE number 780786
• scientific article; zbMATH DE number 1830742
• Faster shortest-path algorithms for planar graphs

Cites work

• scientific article; zbMATH DE number 1303548 (Why is no real title available?)
• scientific article; zbMATH DE number 2079399 (Why is no real title available?)
• scientific article; zbMATH DE number 2080267 (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
• Algorithms and Data Structures
• Blocking for external graph searching
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Finding small simple cycle separators for 2-connected planar graphs
• I/O-efficient point location using persistent B-trees
• Optimal Search in Planar Subdivisions
• Orderly Spanning Trees with Applications
• Planar graph blocking for external searching
• Succinct Representation of Labeled Graphs
• Succinct Representations of Arbitrary Graphs
• Succinct and I/O Efficient Data Structures for Traversal in Trees
• Succinct and I/O efficient data structures for traversal in trees
• Succinct geometric indexes supporting point location queries
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct representations of planar maps
• The book thickness of a graph

Cited in

(6)

• Succinct and I/O Efficient Data Structures for Traversal in Trees
• I/O-efficient contour queries on terrains
• Succinct and I/O efficient data structures for traversal in trees
• I/O and space-efficient path traversal in planar graphs
• I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
• Algorithms and Data Structures

This page was built for publication: I/O-efficient path traversal in succinct planar graphs

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