Short path queries in planar graphs in constant time

DOI10.1145/780542.780565MaRDI QIDQ3581292zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik, Maciej Kurowski

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780565

Mathematics Subject Classification ID

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

Recommendations

• Oracles for bounded-length shortest paths in planar graphs
• scientific article; zbMATH DE number 176745
• Improved distance queries in planar graphs
• Shortest path queries in planar graphs
• Multiple-source shortest paths in planar graphs

Cited in

(20)

• A substring-substring LCS data structure
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Algorithms for finding distance-edge-colorings of graphs
• Oracles for bounded-length shortest paths in planar graphs
• Shortest path queries in planar graphs
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• Constant Time Generation of Biconnected Rooted Plane Graphs
• scientific article; zbMATH DE number 176745 (Why is no real title available?)
• Shortest path queries in digraphs of small treewidth
• Fully dynamic MIS in uniformly sparse graphs
• Near-optimal distance emulator for planar graphs
• I/O-efficient path traversal in succinct planar graphs
• Strip planarity testing for embedded planar graphs
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Short cycles in planar graphs.
• Many distances in planar graphs
• How vulnerable is an undirected planar graph with respect to max flow
• Shortest beer path queries in outerplanar graphs
• How vulnerable is an undirected planar graph with respect to max flow
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs

This page was built for publication: Short path queries in planar graphs in constant time

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