Shortest path queries in planar graphs

DOI10.1145/335305.335359MaRDI QIDQ3192016zbMATH OpenOpenAlexFDO

Authors Danny Z. Chen, Jinhui Xu

Publication date 26 September 2014

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

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

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

• Multiple-source shortest paths in planar graphs
• Short path queries in planar graphs in constant time
• scientific article; zbMATH DE number 176745
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• Planar graphs, negative weight edges, shortest paths, and near linear time

Cited in

(34)

• A substring-substring LCS data structure
• An external memory data structure for shortest path queries
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Reachability oracles for directed transmission graphs
• Multiple-source shortest paths in planar graphs
• Oracles for bounded-length shortest paths in planar graphs
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• Short path queries in planar graphs in constant time
• Querying approximate shortest paths in anisotropic regions
• Shortest path queries in digraphs of small treewidth
• Shortcutting Planar Digraphs
• Encoding shortest paths in spatial networks
• A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
• Shortest-path queries in static networks
• Improved distance queries in planar graphs
• Refined vertex sparsifiers of planar graphs
• Automata, Languages and Programming
• Exact distance oracles for planar graphs
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Algorithms and Computation
• Faster shortest-path algorithms for planar graphs
• Many distances in planar graphs
• A note on reachability and distance oracles for transmission graphs
• Efficient algorithms for shortest path queries in planar digraphs
• Shortest beer path queries in digraphs with bounded treewidth
• A face cover perspective to _1 embeddings of planar graphs
• Almost optimal exact distance oracles for planar graphs
• Faster construction of a planar distance oracle with \(\tilde{O}(1)\) query time

This page was built for publication: Shortest path queries in planar graphs

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