Crossing patterns in nonplanar road networks.
D. Eppstein and
S. Gupta.
arXiv:1709.06113.
Proc. 25th ACM SIGSPATIAL Int. Conf. Advances
in Geographic Information Systems (ACM SIGSPATIAL 2017),
Redondo Beach, California, pp. 40:1–40:9, doi:10.1145/3139958.3139999.
We show that, although an individual edge in a road network can have many crossings, real-world road networks have the property that the crossing graph of their edges is sparse. We prove that networks with this property are themselves sparse and have small separators, allowing many fast algorithms to be generalized from planar graphs to these networks.