# Square-root rule of two-dimensional bandwidth problem

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

- Volume: 45, Issue: 4, page 399-411
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topLin, Lan, and Lin, Yixun. "Square-root rule of two-dimensional bandwidth problem." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.4 (2011): 399-411. <http://eudml.org/doc/273000>.

@article{Lin2011,

abstract = {The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root rule” of the two-dimensional bandwidth, which is useful in evaluating B2(G) for some typical graphs.},

author = {Lin, Lan, Lin, Yixun},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {network layout; two-dimensional bandwidth; lower and upper bounds; optimal embedding; network communication; square root rule; bandwidth minimization problem},

language = {eng},

number = {4},

pages = {399-411},

publisher = {EDP-Sciences},

title = {Square-root rule of two-dimensional bandwidth problem},

url = {http://eudml.org/doc/273000},

volume = {45},

year = {2011},

}

TY - JOUR

AU - Lin, Lan

AU - Lin, Yixun

TI - Square-root rule of two-dimensional bandwidth problem

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2011

PB - EDP-Sciences

VL - 45

IS - 4

SP - 399

EP - 411

AB - The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root rule” of the two-dimensional bandwidth, which is useful in evaluating B2(G) for some typical graphs.

LA - eng

KW - network layout; two-dimensional bandwidth; lower and upper bounds; optimal embedding; network communication; square root rule; bandwidth minimization problem

UR - http://eudml.org/doc/273000

ER -

## References

top- [1] S.N. Bhatt and F.T. Leighton, A framework for solving VLSI graph layout problem. J. Comput. System Sci.28 (1984) 300–343. Zbl0543.68052MR760549
- [2] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Röttger and U.P. Schroeder, Embedding of hypercubes into grids, MFCS’98. Lect. Notes Comput. Sci. 1450 (1998) 693–701. MR1684116
- [3] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Röttger and U.P. Schroeder, The congestion of n-cube layout on a rectangular grid. Discrete Math.213 (2000) 13–19. Zbl0953.68115MR1755405
- [4] P.Z. Chinn, J. Chvátalová, A.K. Dewdney and N.E. Gibbs, The bandwidth problem for graphs and matrices – A survey. J. Graph Theor.6 (1982) 223–254. Zbl0494.05057MR666794
- [5] F.R.K. Chung, Labelings of graphs, in Selected topics in graph theory, L.W. Beineke and R.J. Wilson, Eds. 3 (1988) 151–168. Zbl0656.05058MR1205400
- [6] J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. ACM Comput. Surv.34 (2002) 313–356.
- [7] R. Hochberg, C. McDiarmid and M. Saks, On the bandwidth of triangulated triangles. Discrete Math.138 (1995) 261–265. Zbl0823.05048MR1322101
- [8] Q. Li, M. Tao and Y. Shen, The bandwidth of torus grid graphs Cm × Cn. J. China Univ. Sci. Tech.11 (1981) 1–16. MR701766
- [9] L. Lin and Y. Lin, Two models of two-dimensional bandwidth problems, Inform. Process. Lett.110 (2010) 469–473. Zbl1229.68058MR2667148
- [10] J. Mai and H. Luo, Some theorems on the bandwidth of a graph. Acta Math. Appl. Sinica7 (1984) 86–95. Zbl0542.05052MR768053
- [11] P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, Exact wirelength of hypercubes on a grid. Discrete Appl. Math.157 (2009) 1486–1495. Zbl1172.05330MR2510229
- [12] J. Opatrny and D. Sotteau, Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1. Discrete Appl. Math.98 (2000) 237–254. Zbl0949.05016MR1733674

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.