Many distances in planar graphs

DOI10.1007/s00453-010-9459-0zbMath1239.05046OpenAlexW3139290474MaRDI QIDQ5920250

Sergio Cabello

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

zbMATH Keywords

planar graphsseparatorsdata structuredecomposition of graphsdistances in graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time, A substring-substring LCS data structure, Faster shortest paths in dense distance graphs, with applications, Unnamed Item, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Shortest-path queries in static networks, Unnamed Item, Unnamed Item, Unnamed Item, Single-source shortest paths and strong connectivity in dynamic planar graphs, Non-crossing shortest paths in undirected unweighted planar graphs in linear time, Unnamed Item, Short and Simple Cycle Separators in Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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