Improved methods for analyzing road networks using geometric graph parameters
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Data Structures and AlgorithmsComputational Geometry
Summary
Geometric graphs model things like road networks, and certain numbers called parameters help describe how complex these graphs are. Two important parameters are called c-packedness and λ-low density. The authors figured out how to quickly measure these parameters in very large road networks and discovered they behave quite differently. They also proved some mathematical relationships between them and improved algorithms that use these parameters to find balanced separators, special ways to split the networks. These improvements help build tools that can quickly find exact distances between points on a road network.
What this means in practice
- •For road network engineers: Create more efficient shortest-path query tools by using smaller balanced separators derived from improved parameter computations.
- •For geographic information system developers: Build exact distance oracles that provide fast query responses on large road networks using newly validated graph parameters.
Authors
Gregor Diatzko, Félix Lasseux, Sabine Storandt
Abstract
When designing algorithms for geometric graphs, exploiting structural parameters can lead to significantly improved bounds. Two prominent parameters in this context are $c$-packedness and $λ$-low density, both of which locally restrict graph complexity. Parameterized algorithms based on these parameters have been developed for computing well-separated pair decompositions, balanced separators, as well as distance oracles. Nevertheless the practical applicability of algorithms parameterized by $c$ or $λ$ remains unclear. While $c$-packed and $λ$-low-density graphs have been proposed as realistic models for road networks, the actual parameter values of large real-world instances have so far remained unknown, and existing theoretical guarantees are partially too loose for practical usage. In this paper we first devise scalable implementations for the approximate computation of $c$ and the exact computation of $λ$. Our experiments on road networks with millions of edges reveals a significant gap between the two parameters. On the theoretical side we prove that $c\in O(λ\sqrt n)$ which complements the known result that $λ\in O(c)$. Furthermore we present improved parameterized algorithms for balanced separator computation that reduce the separator size in theory and practice. We also show how to compute a tree decomposition with a width linear in the respective parameterized balanced separator size in polynomial time. This structural result yields a variety of new algorithmic consequences. Among them is an exact distance oracle with query time $O(c)$ for $c$-packed graphs after polynomial-time preprocessing, which improves upon the previous $O(c\log n)$ bound. Our experiments show that the proposed techniques efficiently produce small balanced separators and enable the construction of concise exact distance oracles on large road networks.