
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'
Extremal problems in graph theory, Applied Mathematics, Grids, grids, Planar graphs; geometric and topological aspects of graph theory, embedding, edge-congestion, Graph embedding, Discrete Mathematics and Combinatorics, dilation
Extremal problems in graph theory, Applied Mathematics, Grids, grids, Planar graphs; geometric and topological aspects of graph theory, embedding, edge-congestion, Graph embedding, Discrete Mathematics and Combinatorics, dilation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 19 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
