ACM SIGSPATIAL 2017 (to be held in Southern California in November) doesn’t yet seem to have posted a list of accepted papers, but two of them are mine (one long, one short). I already posted about the short one, “Defining Equitable Geographic Districts in Road Networks via Stable Matching”, so let me just say a little about the other one, now up on the arXiv: “Crossing Patterns in Nonplanar Road Networks” (with UCI grad student Sid Gupta, arXiv:1709.06113).

To begin with, road networks are graphs with a vertex at each intersection of roads and an edge for each segment of road between the intersections. We tend to think of them as being planar graphs, but they’re not. Road segments cross each other, often without an intersection, when one segment is part of an overpass, underpass, or tunnel. Additionally, some pairs of road segments can look like they’re crossing in our data, even when they don’t cross in real life, because the data makes a segment of road look straight when actually it bends around the end of another road.

High Five Interchange at the intersection of I-635 and U.S. Route 75 in Dallas, Texas, looking towards the southwest

But it would be nice if these graphs were planar (even if they aren’t), because then we could apply all the fast algorithms researchers have developed for planar graphs. Many of these algorithms don’t depend on the detailed properties of planarity, but only on the planar separator theorem. So it would be nice if these graphs obeyed a similar separator theorem.

And they do! Or at least, the graphs that fit the model of nonplanar road networks that we use in our new paper do have good separators. Our idea is that most of the time when roads cross they do so in isolation; a crossing road segment would often only cross one other road segment. If that were true everywhere, we’d get the 1-planar graphs, but there are a few segments that cross multiple others (think of the long tunnels under Boston, or complicated freeway interchanges such as the one in Dallas above). Even in those cases, though, the collection of road segments that cross each other has a restricted patterns. In a long tunnel, for instance, a single segment may cross many others, but each of those other crossed segments will typically be much shorter and have no other crossings.

We can understand these crossing patterns more clearly by drawing another graph, the crossing graph, which has a vertex for each road segment and an edge connecting it to each other road segment that it crosses. Most vertices are isolated (they don’t cross anything) and most edges are isolated (they connect two road segments that cross each other and nothing else). There are occasional larger connected components, but these still have a simple structure. We thought going into this research that they would all be trees; that’s not true, but they do all have low degeneracy. That means, in any cluster of crossing road segments, at least one of the segments is crossed only a small number of times. Remove that segment, and the remaining segments still have one that’s crossed only few times, and so on. We tested the degeneracy of the road networks of many cities, and we never saw a number higher than 6 (in Buenos Aires). For most cities the number was even smaller, 3 or 4. And the number of non-tree clusters of crossing road segments was always a small fraction of all crossings. We tried including only the crossings we new were real (by using the identification of some road segments as bridges or tunnels in the data we used) or looking at all the crossings, even the artificial ones caused by differences between the straight segments of the data and the curvature of the actual road segments; it didn’t make much difference to our overall results.

We also show (by using the crossing number inequality) that road networks with \(d\)-degenerate crossing graphs are sparse (they have \(O(nd^{1/2})\) edges and \(O(nd^{3/2})\) crossings). It follows that they have small separators, inherited from the separators of their planarizations. So I think the graphs with degenerate crossing graphs make a good model to look for algorithms on: not so restrictive (like planar or 1-planar graphs) that it eliminates the real-world graphs we’re trying to model, but restrictive enough to have properties useful in algorithm design.