Efficient embeddings of grids into grids
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\). NEWLINENEWLINENEWLINEThe 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. NEWLINENEWLINENEWLINEIn 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.
- A new combinatorial approach to optimal embeddings of rectangles
- Compressions and isoperimetric inequalities
- Edge isoperimetric theorems for integer point arrays
- Embedding grids into grids: Techniques for large compression ratios
- Embedding of Grids into Optimal Hypercubes
- scientific article; zbMATH DE number 4147467 (Why is no real title available?)
- scientific article; zbMATH DE number 736286 (Why is no real title available?)
- On Embedding Rectangular Grids in Square Grids
- On embedding rectangular meshes into rectangular meshes of smaller aspect ratio
- Optimal labelling of a product of two paths
- Optimal numberings and isoperimetric problems on graphs
- The congestion of \(n\)-cube layout on a rectangular grid
- Exact wirelength of hypercubes on a grid
- The hardness of embedding grids and walls
- Embedding grids in surfaces
- Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
- The congestion of \(n\)-cube layout on a rectangular grid
- A linear time algorithm for embedding hypercube into cylinder and torus
- Separator-based graph embedding into multidimensional grids with small edge-congestion
- Embedding linear orders in grids
- Embedding of the folded hypercubes into tori
- scientific article; zbMATH DE number 1706200 (Why is no real title available?)
- Embeddings of circulant networks
- Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
- scientific article; zbMATH DE number 1262803 (Why is no real title available?)
- Compressing grids into small hypercubes
- Embedding of hypercubes into necklace, windmill and snake graphs
- scientific article; zbMATH DE number 1760104 (Why is no real title available?)
- EPG-representations with Small Grid-Size
- Embedding grids into grids: Techniques for large compression ratios
- Bothway embedding of circulant network into grid
- scientific article; zbMATH DE number 7250384 (Why is no real title available?)
- Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees
- Embedding Wheel - like Networks
- On embedding 2-dimensional toroidal grids into de Bruijn graphs with clocked congestion one
- Embedding multidimensional grids into optimal hypercubes
This page was built for publication: Efficient embeddings of grids into grids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5928873)
