Many distances in planar graphs
From MaRDI portal
Publication:5920250
DOI10.1007/s00453-010-9459-0zbMath1239.05046MaRDI QIDQ5920250
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9459-0
05C10: Planar graphs; geometric and topological aspects of graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
68P05: Data structures
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Shortest-path queries in static networks, Short and Simple Cycle Separators in Planar Graphs, Unnamed Item, Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., A substring-substring LCS data structure, Faster shortest paths in dense distance graphs, with applications, Single-source shortest paths and strong connectivity in dynamic planar graphs, Non-crossing shortest paths in undirected unweighted planar graphs in linear time
Cites Work
- The design of dynamic data structures
- Planar separators and parallel polygon triangulation.
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Finding small simple cycle separators for 2-connected planar graphs
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Shortest paths in directed planar graphs with negative lengths
- Shortest path queries in planar graphs
- Short path queries in planar graphs in constant time
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- Planar graph decomposition and all pairs shortest paths
- Approximating the Stretch Factor of Euclidean Graphs
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Compact oracles for reachability and approximate distances in planar digraphs
- Many distances in planar graphs
- Faster shortest-path algorithms for planar graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item