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

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)\) . Let \(D(G)=\max _{(u,v)}\delta _G(u,v)\) , for \((u,v)\in V\times V\) , which is called the diameter of G. Given a disconnected road network modelled as two disjoint trees \(T_1\) and \(T_2\) , this paper first aims at inserting one or two edges (bridges) between them to minimize the (constrained) diameter \(D(T_1\cup T_2\cup I_j)\) going through the inserted edges, where \(I_j, j=1,2\) , is the set of inserted edges with \(|I_1|=1\) and \(|I_2|=2\) . The corresponding problems are called the optimal bridge and twin bridges problems. Since when more than one edge are inserted between two trees the resulting graph becomes more complex, for the general network G we consider the problem of inserting a minimum of k edges such that the shortest distances \(\delta _G(u_i,v_i)\) between a given set of m pairs of points \(P=\{(u_i,v_i)\mid u_i,v_i\in V, i\in [m]\}\) are all decreased. The main results of this paper are summarized as follows: