# Square-root rule of two-dimensional bandwidth problem∗

RAIRO - Theoretical Informatics and Applications (2012)

- 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 45.4 (2012): 399-411. <http://eudml.org/doc/222097>.

@article{Lin2012,

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},

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

language = {eng},

month = {1},

number = {4},

pages = {399-411},

publisher = {EDP Sciences},

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

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

volume = {45},

year = {2012},

}

TY - JOUR

AU - Lin, Lan

AU - Lin, Yixun

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2012/1//

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 layout; network communication; square root rule; bandwidth minimization problem; optimal embedding

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

ER -

## References

top- S.N. Bhatt and F.T. Leighton, A framework for solving VLSI graph layout problem. J. Comput. System Sci.28 (1984) 300–343. Zbl0543.68052
- 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.
- 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.68115
- 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.05057
- 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.
- J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. ACM Comput. Surv.34 (2002) 313–356.
- R. Hochberg, C. McDiarmid and M. Saks, On the bandwidth of triangulated triangles. Discrete Math.138 (1995) 261–265. Zbl0823.05048
- Q. Li, M. Tao and Y. Shen, The bandwidth of torus grid graphs Cm × Cn. J. China Univ. Sci. Tech.11 (1981) 1–16.
- L. Lin and Y. Lin, Two models of two-dimensional bandwidth problems, Inform. Process. Lett.110 (2010) 469–473. Zbl1229.68058
- J. Mai and H. Luo, Some theorems on the bandwidth of a graph. Acta Math. Appl. Sinica7 (1984) 86–95. Zbl0542.05052
- P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, Exact wirelength of hypercubes on a grid. Discrete Appl. Math.157 (2009) 1486–1495. Zbl1172.05330
- 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.05016

## NotesEmbed ?

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