Efficient embeddings of grids into grids (Q5928873)

An embedding of a graph \(G\) into a graph \(H\) is a pair of two mappings: an injection \(\phi:V_G\mapsto V_H\) and a routing scheme that maps \(E_G\) into the set of paths in \(H\). The authors consider two embedding parameters: dilation, defined as the length of a longest path in the image of the routing scheme, and the edge-congestion, defined as the maximum over \(e\in E_H\) of the number of paths in the image of the routing scheme that contain \(e\). The authors construct embeddings of 2-dimensional \(h\times w\) grids into \(h'\times w'\) grids (with \(h'w'\geq hw\)) which are optimal with respect to the dilation or edge-congestion. The situation depends on two cases: \(h'<h\leq w<w'\) and \(h<h'\leq w'<w\). In the first case a lower bound for the dilation has been derived that matches a known constructive upper bound. A new construction provides an embedding with the edge-congestion that might exceed the optimal one at most by one. The lower bounds for the involved parameters are based on graph isoperimetric problems. In the second case new constructions provide embeddings with dilation at most 5 and edge-congestion at most 4. In many cases the edge-congestion can be lowered down to 2 or to 3.