An efficient oracle for counting shortest paths in planar graphs

DOI10.1007/978-3-030-93176-6_35zbMath1502.68227OpenAlexW4205679529MaRDI QIDQ5970820

Ye Gong, Qian-Ping Gu

Publication date: 1 July 2022

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-93176-6_35

zbMATH Keywords

planar graphsVoronoi diagramscomputational studydistance oracles

Mathematics Subject Classification ID

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

Related Items

An efficient oracle for counting shortest paths in planar graphs

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• Finding small simple cycle separators for 2-connected planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Shortest-path queries in static networks
• Almost optimal distance oracles for planar graphs
• Structured recursive separator decompositions for planar graphs in linear time
• Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs
• Faster shortest-path algorithms for planar graphs