1. Questions

Planar graph representations are widely used in urban road-network analysis because they simplify the study of connectivity, centrality, and routing structure. A planar graph can be embedded in the plane so that edges intersect only at shared endpoints (Fritsch and Fritsch 1998), a property on which many graph-theoretic methods depend, including cycle–cut duality and related results for planar graphs (Whitney 1932; Kasteleyn 1961). Real road networks frequently violate it, because overpasses, underpasses, elevated expressways, and multi-level interchanges create crossings where roads do not physically meet (Boeing 2020). Geographic non-planarity must nevertheless be distinguished from graph-theoretic non-planarity. The former concerns whether mapped road geometries cross; the latter concerns whether the abstract network admits any crossing-free embedding, irrespective of the original coordinates. This study addresses the latter.

Forcing such a network into planar form requires that edges be removed, reshaped, or replaced with artificial nodes. These operations are usually treated as a technical convenience, but they alter the object being measured through which urban form is subsequently interpreted.

Three questions follow. First, how much distortion does planar approximation introduce in real urban road networks? Second, are some network metrics substantially more sensitive to it than others? Third, can the magnitude of distortion be anticipated from properties of the original network, that is, from its baseline topological scale, or only from the intensity of edge exclusion that the planarity constraint imposes?

2. Methods

Road networks were extracted from OpenStreetMap using OSMnx (Geoff Boeing 2017). Primary, secondary, trunk, and associated link roads were included, while motorways were excluded to focus on intra-urban network structure. Each city was represented as an undirected graph G=(V,E) in which intersections are nodes and road segments are edges, and only the largest connected component was retained. The complete node and edge datasets used for all 40 cities are publicly available at https://github.com/Todai-ops/Planarization-in-Urban-Road-Networks.

Planar counterparts were constructed using a greedy maximal planar sub-graph procedure guided by edge betweenness centrality, which measures how often an edge lies on shortest paths between node pairs. Edges with higher values were treated as more important for maintaining shortest-path connectivity. Prioritizing them makes the resulting sub-graph a conservative estimate of distortion, since an arbitrary or geometry-based ordering would discard shortest-path-critical edges more often and would inflate the measured effect.

Edge betweenness centrality was computed for every edge in the original network; edges were ranked from highest to lowest; and edges were then added one at a time to an initially empty graph on the full node set, each addition being retained only if it preserved planarity. This construction does not guarantee connectivity and was therefore verified for each city: the resulting sub-graph spanned the original node set and remained connected in all 40 cases.

Original and planarized networks were compared using six metrics: density (observed relative to possible edges), mean clustering coefficient (interconnection among neighbouring nodes), diameter (longest shortest path), mean straightness centrality (Euclidean-to-network distance ratio), global efficiency (mean reciprocal shortest-path length), and average shortest-path cost (mean pairwise shortest-path cost). The last three are not mutually independent, as each is a function of shortest-path length; they are reported together for comparability with existing work rather than as separate lines of evidence. Since the node set is unchanged, the proportional change in density equals the proportion of edges excluded, which is referred to below as edge loss.

For each city and metric, the original value, planarized value, and percentage change were calculated. Cross-city variation in the change in average shortest-path cost was assessed using Spearman correlation and ordinary least squares regression, with edge loss, original diameter, and original average shortest-path cost as candidate predictors: the first measures the intensity of the planarity constraint, and the latter two represent baseline topological scale. The implementation was checked using the two canonical non-planar Kuratowski graphs, K3,3 and K5. In both cases, the procedure removed edges until the resulting graph satisfied the graph-theoretic planarity condition while remaining connected. Robustness to alternative edge-ordering rules was not assessed; therefore, the magnitudes reported below are specific to the betweenness-prioritised heuristic.

3. Findings

Under the applied heuristic, planarization increased average shortest-path cost in every city, by a mean of 12.77% (median 10.85%, IQR 3.30–16.16), ranging from 0.21% in Auckland to 53.41% in Shanghai (Table 1). The distribution is right-skewed, so the mean overstates the typical case.

Table 1.Percentage changes in the six network metrics for all 40 cities. Positive values represent increases, and negative values represent decreases after planar sub-graph extraction.
City ΔρΔρ ΔCΔC ΔDΔD ΔSΔS ΔEgΔEg ΔˉTΔˉT
Abu Dhabi −6.05 −10.98 +2.09 −15.55 −10.99 +11.02
Auckland −0.65 −0.76 0.00 −0.55 −0.48 +0.21
Bangkok −15.71 −22.14 +20.87 −23.49 −23.86 +39.33
Beijing −6.27 −8.41 +26.13 −13.04 −9.76 +13.89
Bergen −5.92 −7.18 +2.06 −10.28 −6.22 +12.56
Berlin −5.14 −4.03 +1.23 −11.05 −8.87 +15.46
Brisbane −2.09 −2.03 0.00 −5.64 −5.64 +6.91
Brussels −4.61 −1.38 0.00 −3.61 −3.44 +1.86
Chicago −3.14 −2.35 0.00 −2.47 −2.16 +1.43
Cologne −6.72 −8.94 +8.24 −12.11 −10.42 +14.14
Dhaka −6.63 −7.58 +4.23 −8.62 −6.08 +4.93
Doha −6.02 −10.07 +1.90 −19.74 −12.68 +28.19
Dubai −6.84 −7.64 +8.51 −16.73 −9.88 +18.24
Hamburg −4.77 −3.26 0.00 −9.05 −6.06 +14.52
Hong Kong −9.83 −1.69 0.00 −14.27 −13.41 +11.67
Lyon −11.37 −20.54 0.00 −11.22 −7.82 +13.86
Madrid −4.03 −5.76 0.00 −6.62 −4.59 +8.04
Melbourne −0.86 −1.03 0.00 −2.27 −1.25 +2.30
Mumbai −10.20 −12.44 +13.33 −12.21 −12.81 +14.16
Munich −14.64 −15.55 +16.07 −17.11 −15.50 +25.56
Nagoya −3.81 −4.22 0.00 −1.76 −1.76 +1.87
Osaka −10.95 −27.67 +8.33 −17.63 −12.96 +26.02
Reykjavík −4.40 −2.32 0.00 −5.73 −4.56 +7.13
Riga −10.36 −13.93 +1.96 −14.01 −9.56 +19.08
Santiago −2.01 −3.22 0.00 −1.70 −1.64 +1.51
São Paulo −9.92 −11.78 0.00 −18.00 −13.54 +22.24
Seville −2.68 −3.31 +6.85 −3.53 −3.49 +7.78
Shanghai −18.47 −15.62 +17.89 −33.41 −27.48 +53.41
Shenzhen −9.80 −10.09 +12.14 −22.89 −15.12 +34.26
Singapore −5.70 −8.54 +11.51 −15.61 −12.28 +20.45
Stockholm −2.45 −4.93 0.00 −0.80 −2.34 +0.51
Strasbourg −7.17 −6.36 0.00 −10.73 −7.56 +10.67
Sydney −2.93 −3.29 +1.65 −4.22 −3.93 +4.48
Tallinn −7.83 −9.62 0.00 −9.68 −8.85 +14.75
Tokyo −10.30 −12.93 +6.09 −9.43 −8.23 +9.22
Toronto −1.87 −1.40 0.00 −1.88 −1.23 +2.12
Vancouver −3.74 −5.59 0.00 −1.94 −2.26 +1.66
Wellington −2.53 −2.47 0.00 −4.79 −4.49 +3.19
Yokohama −8.68 −9.53 0.00 −7.81 −6.35 +9.01
Zurich −2.37 +1.78 0.00 −3.12 −1.90 +3.34

Sensitivity differed sharply across metrics. Straightness centrality and global efficiency fell by 10.11% and 8.04%, respectively, closely tracking the increase in cost (ρ=−0.950 and −0.919), as expected given their shared dependence on shortest-path length. Diameter was the exception, remaining unchanged in 21 cities (52.5%, median 0%). This stability reflects its status as a single-pair extremum rather than an absence of distortion: Beijing’s diameter rose by 26.13% while its average cost rose by only 13.89%. Diameter is therefore the least informative of the six metrics for detecting planarization effects, not the most robust.

Grouping cities into sample-derived thirds by their cost increases, rather than by fixed thresholds, reveals a monotonic gradient across all path-based metrics. Mean edge loss rises from 2.84% in the lower third (0.21–6.91%; 14 cities; mean cost increase 2.59%) to 7.20% in the middle third (7.13–14.16%; 13 cities; 11.01%) and 9.70% in the upper third (14.52–53.41%; 13 cities; 25.50%), while mean straightness falls by 3.10%, 10.19%, and 17.57% respectively. The largest effects occur in densely grade-separated networks such as Shanghai, Shenzhen, Bangkok, and Doha, and the smallest in predominantly at-grade gridded networks such as Auckland, Melbourne, Chicago, and Toronto, despite the exclusion of motorways from all networks.

Distortion was associated with edge exclusion rather than with baseline topological scale. Edge loss predicted the increase in cost strongly (Spearman’s ρ=0.797, p<0.001), with the corresponding regression explaining 69.6% of cross-city variation (R2=0.696), such that each additional percentage point of edge loss was associated with a 2.33-percentage-point increase in cost (95% CI: 1.82–2.84). Neither original diameter (ρ=0.123, p=0.449) nor original average shortest-path cost (ρ=0.072, p=0.660) showed a detectable association at n=40.

Acknowledgements

The authors thank the editors and anonymous reviewers for their constructive comments, which improved the manuscript.