Skip to content

2D Grid Routing Tightness

Claim/Theorem

For a \(p\times q\) rectangular grid graph, the routing number is \(O(p+q)\); more generally, for connected convex grid pieces the routing number is \(\Theta(w+h)\) in terms of width and height. Therefore for a near-square 2D grid with \(N\) vertices, generic token routing requires and suffices up to constants in depth \(\Theta(\sqrt{N})\). This shows that the lower bound sought in Conjecture 3 matches the intrinsic routing scale of static 2D meshes rather than being an artifact of an especially poor routing strategy.

Dependencies

  • None.

Conflicts/Gaps

  • Routing number concerns permutation routing by parallel swaps, not arbitrary coherent syndrome-extraction circuits.
  • This node supports the sharpness of the Omega(sqrt(n)) barrier but does not itself prove that an expander-style Tanner round reduces to worst-case grid routing.
  • The upper bound is qualitative support for tightness, not part of the lower-bound proof.

Sources

  • 10.1016/j.comgeo.2022.101862
  • 10.1145/167088.167239