Crossing Patterns in Nonplanar Road Networks

David Eppstein, Siddharth Gupta

We define the crossing graph of a given embedded graph (such as a road network) to be a graph with a vertex for each edge of the embedding, with two crossing graph vertices adjacen…