I/O-efficient path traversal in succinct planar graphs

DOI10.1007/S00453-015-0086-7zbMATH Open1364.68305OpenAlexW2281191978MaRDI QIDQ521807FDOQ521807

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

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

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)

Cites Work

• Optimal Search in Planar Subdivisions
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• The book thickness of a graph
• Title not available (Why is that?)
• Finding small simple cycle separators for 2-connected planar graphs
• Title not available (Why is that?)
• Succinct Representations of Arbitrary Graphs
• Orderly Spanning Trees with Applications
• Algorithms and Data Structures
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• Succinct representations of planar maps
• 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 and I/O Efficient Data Structures for Traversal in Trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Succinct Representation of Labeled Graphs
• I/O-efficient point location using persistent B-trees

Cited In (5)

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

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)