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.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.