A well-separated pair decomposition for low density graphs

Low density graphs are considered to be a realistic graph class for modelling road networks. It has advantages over other popular graph classes for road networks, such as planar graphs, bounded highway dimension graphs, and spanners. We believe that low density graphs have the potential to be a useful graph class for road networks, but until now, its usefulness is limited by a lack of available tools.

In this paper, we develop two fundamental tools for low density graphs, that is, a well-separated pair decomposition and an approximate distance oracle. We believe that by expanding the algorithmic toolbox for low density graphs, we can help provide a useful and realistic graph class for road networks, which in turn, may help explain the many efficient and practical heuristics available for road networks.

Advances in technology have made the collection of geographic data easier than ever before. Nowadays, continent-sized road networks are stored in graphs with up to a billion vertices and edges. To analyse these large graphs, highly efficient algorithms and data structures are required.

Many heuristics for analysing road networks are highly efficient in practice. One explanation as to why many heuristics are efficient on road networks but inefficient on general graphs is that these heuristics can exploit the underlying properties of road networks. For example, experiments show that road networks have desirable underlying properties such as small separators [37,39] and bounded maximum degree [20,43]. A common structure that exists for road networks that does not exist for general graphs is an efficient shortest path data structure [7,18,54,62].

Many attempts have been made to explain why road networks have desirable properties such as small separators and efficient shortest path data structures. In the theory community, a popular approach is to argue that road networks belong to a certain graph class, and then to prove a set of desirable properties for the graph class. Numerous graph classes have been proposed for road networks. When assessing these graph classes, it is natural to consider two criteria [44].

Criterion 1 (Usefulness). How well does this graph class explain the desirable properties of road networks? Do graphs in this graph class have small separators, or efficient shortest path data structures?

Criterion 2 (Realism). How well does this graph class model real-world road networks? Do all, or most, real-world road networks belong to this graph class?

Planar graphs, bounded highway dimension graphs, and spanners are among the most popular graph classes for road networks 1 . Next, we will assess these popular graph classes using Criteria 1 and Criteria 2. Then, we will introduce low density graphs, which is our preferred graph class for road networks.