I/O-efficient path traversal in succinct planar graphs

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

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 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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Finding small simple cycle separators for 2-connected planar graphs
• 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
• Succinct Representation of Labeled Graphs
• I/O-efficient point location using persistent B-trees

Cited In (1)

• I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths

Recommendations

• Faster shortest-path algorithms for planar graphs 👍 👎
• Short path queries in planar graphs in constant time 👍 👎
• I/O and Space-Efficient Path Traversal in Planar Graphs 👍 👎
• I/O-Optimal Algorithms for Outerplanar Graphs 👍 👎
• I/O-efficient algorithms on near-planar graphs 👍 👎
• Algorithms - ESA 2003 👍 👎
• I/O-Efficient Algorithms on Near-Planar Graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)