Improved distance queries in planar graphs

DOI10.1007/978-3-642-22300-6_54zbMATH Open1342.68113arXiv1012.2825OpenAlexW1792146362MaRDI QIDQ5199280FDOQ5199280

Authors: Yahav Nussbaum 

Publication date: 12 August 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: There are several known data structures that answer distance queries between two arbitrary vertices in a planar graph. The tradeoff is among preprocessing time, storage space and query time. In this paper we present three data structures that answer such queries, each with its own advantage over previous data structures. The first one improves the query time of data structures of linear space. The second improves the preprocessing time of data structures with a space bound of O(n^(4/3)) or higher while matching the best known query time. The third data structure improves the query time for a similar range of space bounds, at the expense of a longer preprocessing time. The techniques that we use include modifying the parameters of planar graph decompositions, combining the different advantages of existing data structures, and using the Monge property for finding minimum elements of matrices.

Full work available at URL: https://arxiv.org/abs/1012.2825

Recommendations

• Exact distance oracles for planar graphs
• Multiple-source shortest paths in planar graphs
• Shortest path queries in planar graphs
• scientific article; zbMATH DE number 176745

Mathematics Subject Classification ID

Data structures (68P05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Cited In (12)

• Faster shortest paths in dense distance graphs, with applications
• Efficient Point-to-Point Resistance Distance Queries in Large Graphs
• Exact distance oracles for planar graphs
• Improved Distance Queries and Cycle Counting by Frobenius Normal Form
• Shortest-path queries in static networks
• Short path queries in planar graphs in constant time
• Approximate Distance Queries in Disk Graphs
• Title not available (Why is that?)
• Reactive proximity data structures for graphs
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time

This page was built for publication: Improved distance queries in planar graphs

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