Two models of two-dimensional bandwidth problems. (English) Zbl 1229.68058
Summary: The two-dimensional bandwidth problem is to embed a graph \(G\) into an \(n\times n\) grid in the plane such that the maximum distance between adjacent vertices is as small as possible. Here, the “distance” has two different meanings: the \(L_{1}\)-norm distance and \(L_{\infty }\)-norm distance. So we have two models of two-dimensional bandwidth problem. This paper investigates the basic properties and relations of these two models. Some lower bounds, upper bounds, and exact results are presented.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C12 | Distance in graphs |
References:
| [1] | Bhatt, S. N.; Leighton, F. T., A framework for solving VLSI graph layout problem, J. Computer and System Sciences, 28, 2, 300-343 (1984) · Zbl 0543.68052 |
| [2] | Bhatt, S. N.; Cosmadakis, S., The complexity of minimizing wire lengths in VLSI layouts, Information Processing Letters, 25, 263-267 (1987) · Zbl 0653.68020 |
| [3] | Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; Gibbs, N. E., The bandwidth problem for graphs and matrices - A survey, J. Graph Theory, 6, 223-254 (1982) · Zbl 0494.05057 |
| [4] | Chung, F. R.K., Labelings of graphs, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, vol. 3 (1988)), 151-168 · Zbl 0656.05058 |
| [5] | Diaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM Computing Surveys, 34, 313-356 (2002) |
| [6] | Lai, Y. L.; Williams, K., A survey of solved problems and applications on bandwith, edgesum, and profile of graphs, J. Graph Theory, 31, 75-94 (1999) · Zbl 0924.05058 |
| [7] | Lin, Y., Two-dimensional bandwidth problem, (Alavi, Y.; etal., Combinatorics, Graph Theory, Algorithms and Applications (1994), World Scientific), 223-232 |
| [8] | Lin, Y., On density lower bounds of two-dimensional bandwidth, J. Mathematical Research and Exposition, 16, 3, 343-349 (1996) · Zbl 0902.05066 |
| [9] | Lin, Y.; Hao, J.; Li, X., Two-dimensional bandwidth problem under distance of \(L_\infty \)-norm, OR Transactions, 4, 3, 8-12 (2000) |
| [10] | Opatrny, J.; Sotteau, D., Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1, Discrete Applied Math., 98, 237-254 (2000) · Zbl 0949.05016 |
| [11] | Syslo, M. M.; Zak, J., The bandwidth problem: Critical subgraphs and the solution for caterpillars, Annals of Discrete Math., 16, 281-286 (1982) · Zbl 0494.05058 |
| [12] | Yeh, C. H.; Parhami, B., VLSI layouts of complete graphs and star graphs, Information Processing Letters, 68, 39-45 (1998) · Zbl 1339.68216 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
