Many distances in planar graphs

DOI10.1007/s00453-010-9459-0zbMath1239.05046MaRDI 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 graphs; separators; data structure; decomposition of graphs; distances in graphs

Mathematics Subject Classification ID

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