# “Converting” networkx / osmnx graph to a planar graph

I am currently working on some analyses of the Berlin road network, and I am using OSMNX to get a relevant graph representation. I noticed that - if with drawbacks - many authors use planar representations when working with road networks. Geoff Boeing, the author of osmnx, has concerned himself with the issue, too (https://geoffboeing.com/publications/planarity-street-network-representation/, here for full text).

So suppose I have a non-planar graph, what would be the easiest way to make it planar? More specifically, I would like to make it planar by adding nodes at places where edges intersect, instead of removing edges until the graph is planar, as suggested elsewhere. Do you know of any algorithm in python that is able to do that?

I found that, in some instances, downloading the raw (non-simplified) data from OSM using OSMNX, one obtains a planar graph of a place, however, this is not the case for Berlin as a whole.

I would be very happy about any hints, suggestions, and help given. Thanks!

• Asking about algorithms is fine, but questions about specific implementations or Python are off-topic here. If you're asking for a recommendation for a software package or library, that's off-topic here.
– D.W.
Jul 6, 2021 at 7:37
• – D.W.
Jul 6, 2021 at 7:39
• Thanks for the info, in the other post as well, and of course for the answer. I've learned something today
– Ben
Jul 6, 2021 at 13:45

The Bentley-Ottmann algorithm can be used to find all intersections between edges, and then you can add a node at each such intersection.

The algorithm consists of converting a Voronoi diagram, which is a partitioning of a plane into regions based on the distance to points in a specific subset of the plane, into a weighted graph represented by a networkx object in Python.

The input to the algorithm is a list of points in two dimensions. The Voronoi diagram is computed using the scipy.spatial library, which returns a set of vertices and edges representing the diagram.

The algorithm then iterates through the edges of the Voronoi diagram and checks if each edge connects two points whose coordinates lie in the range [0,1]. If so, the edge is added as an edge in the networkx graph, with a weight equal to the Euclidean distance between the two endpoints of the edge.

Finally, the resulting networkx graph is returned as output. This graph represents the Voronoi diagram as a weighted graph, where the vertices correspond to the points in the input list and the edges represent the borders between the Voronoi regions. The weights on the edges represent the lengths of these borders.

The algorithm for converting a Voronoi diagram into a weighted networkx graph is useful for generating planar graphs in several ways.

Firstly, the Voronoi diagram itself can be thought of as a planar graph, where the vertices represent the input points and the edges represent the borders between the Voronoi regions. This graph can be used for various applications, such as geographic information systems, computer vision, and computational geometry.

import numpy as np
import networkx as nx
from scipy.spatial import Voronoi,voronoi_plot_2d
import matplotlib.pyplot as plt

#we create a function to generate a planar graph from a voronoi diagram

def voronoi_to_networkx(points):
# we get the voronoi diagram
vor = Voronoi(points)

G = nx.Graph()

# Add an edge for each ridge in the Voronoi diagram that connects two points in the range [0,1]
for simplex in vor.ridge_vertices:
if -1 not in simplex:
i, j = simplex
p = vor.vertices[i]
q = vor.vertices[j]
if 0 <= p[0] <= 1 and 0 <= p[1] <= 1 and 0 <= q[0] <= 1 and 0 <= q[1] <= 1:
distance = np.linalg.norm(p - q) # Calculate the Euclidean distance between p and q

return G

#We create 20 points from which the voronoi diagram will be generated
points=np.random.rand(20,2)

#we plot the diagram
vor=Voronoi(points)
voronoi_plot_2d(vor)
plt.show()

#We convert diagram to networkx
graph=voronoi_to_networkx(points)
#We assign each node to its actual position in the plane
pos = dict(zip(graph.nodes(), graph.nodes()))
nx.draw(graph, pos,node_size=5)
#We check that the graph is planar.
print(nx.is_planar(graph))
plt.show()