paper · 2026
Constraint-Efficient Routing via Dual Graph on Address Hierarchy
Standard routing graphs split intersection nodes for every constraint — turn restriction, time-of-day, vehicle class. Node count grows multiplicatively. The Dual Graph encodes constraints as edge attributes; node count stays fixed. On Seoul: intra-district routing in 0.9 ms, cross-district hierarchical routing in 3.84 ms — 5.3× faster than flat Dijkstra.
What this paper does
Routing under real-world constraints — turn restrictions, time-of-day rules, vehicle-class conditions — causes node proliferation in conventional Primal Graph representations. Each constrained intersection must be split into multiple via-nodes, inflating the graph super-linearly with constraint count. Under combined constraints (the standard regime in autonomous driving), this routinely violates real-time latency budgets.
This paper builds a Dual Graph natively on the Korean Road Name Address three-tier hierarchy (daero / ro / gil). Named roads are nodes. Inter-road intersections are edges. Constraints become edge attributes — the node count |V_D| is invariant under any number of additional constraints.
The theorem
For the Dual Graph: |V_D(k)| = |V_D| for all k ≥ 0.
For the Primal Graph with node splitting: |V_P(k)| ≈ |V_P| · d̄^(k/d̄), where d̄ is mean intersection degree and k is the constraint type count.
For Gangnam-gu (mean degree 12.6, 158 Primal nodes, 876 Dual nodes), the crossover where Dual becomes smaller than Primal occurs at roughly 2.1 constraint types — routinely exceeded in real urban deployments.
| Turn-restriction rate | Primal nodes | Dual nodes | Dual advantage |
|---|---|---|---|
| 0% | 158 | 876 | — |
| 1% | 203 | 876 | 4.3× |
| 5% | 561 | 876 | 1.6× |
| 10% | 1,997 | 876 | 2.3× |
| 20% | 25,243 | 876 | 28.8× |
Empirical results — Seoul (25 districts)
The full Seoul Dual Graph: 13,633 nodes, 3,378 backbone edges (road_conn), 18,995 terminal edges (intrsct_index).
| Scope | Nodes | p50 | p95 | avg pops |
|---|---|---|---|---|
| Gangnam-gu (intra-district) | 876 | 0.90 ms | 1.58 ms | 558 |
| Seoul — flat single graph | 16,107 | 20.41 ms | 43.92 ms | 5,991 |
| Seoul — hierarchical | 3,355 | 3.84 ms | 9.38 ms | 219 |
The hierarchical scheme uses pre-computed boundary shortcuts (sig_paths) and inter-district edges (sig_exit). Cross-district routing reduces to Dijkstra over 3,355 boundary nodes instead of the full 16,107. The 5.3× speedup arises directly from the RNADDR system’s administrative partitioning — district boundaries provide natural decomposition points.
Topological reframing
A side observation, but possibly the most consequential one: the existing RNADDR system manages points (building addresses) as primary objects. Roads and districts are identifiers, not managed entities.
This work formalises roads as 1-cells with line attributes A_1(r) and districts as 2-cells with face attributes A_2(f). Queries that previously required PostGIS or a GIS server — which roads in this district exceed a congestion threshold? what is the accessibility score of this zone? find all buildings reachable within 10 minutes from an indoor entrance — become first-class operations on the attributed cell complex.
Status
Second in a three-paper series. Korean patent application No. 10-2026-0039486 (filed 2026-03-05). PCT international filing planned.