Optimal Bridge, Twin Bridges and Beyond: Inserting Edges into a Road Network to Minimize the Constrained Diameters

Zhidan Feng, Henning Fernau, Binhai Zhu

Given a road network modelled as a planar straight-line graph $G=(V,E)$ with $|V|=n$, let $(u,v)\in V\times V$, the shortest path (distance) between $u,v$ is denoted as ${\delta }_G(u,v)$.…