Square-root rule of two-dimensional bandwidth problem∗
1 School of Electronics and Information Engineering, Tongji University, Shanghai 200092, P.R. China
2 The Key Laboratory of Cognitive Radio and Information Processing, Ministry of Education, Guilin University of Electronic Technology, Guilin 541004, P.R. China
3 Department of Mathematics, Zhengzhou University, Zhengzhou 450052, P.R. China
Received: 26 February 2011
Accepted: 2 August 2011
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.
Mathematics Subject Classification: 05C78 / 68R10
Key words: Network layout / two-dimensional bandwidth / lower and upper bounds / optimal embedding.
© EDP Sciences 2011