A survey of graph layout problems

ABSTRACT

Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Emile Aarts , Jan K. Lenstra, Local Search in Combinatorial Optimization, John Wiley & Sons, Inc., New York, NY, 1997
	2	Adolphson, D. 1977. Single machine job sequencing with precedence constraints. SIAM J. Comput. 6, 40--54.
	3	Adolphson, D. and Hu, T. C. 1973. Optimal linear ordering. SIAM J. Appl. Mathem. 25, 3, 403--423.
	4	Alon, N. and Milman, V. 1985. λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combinatorial Theory. Series B 38, 73--88.
	5	Àlvarez, C., Cases, R., Díaz, J., Petit, J., and Serna, M. 2000. Routing trees problems on random graphs. In Approximation and Randomized Algorithms in Communication Networks, J. Rolim et al., Ed. ICALP Workshops 2000. Carleton Scientific, 99--111.
	6	Àlvarez, C., Díaz, J., and Serna, M. 1998. Intervalizing colored graphs is NP-complete for caterpillars with hair length 2. Technical report LSI 98-9-R, Dept. de Llenguatges i Sistemes Informàtics, Univ. Politècnica de Catalunya.
	7	Àlvarez, C., Díaz, J., and Serna, M. 2001. The hardness of intervalizing four colored caterpillars. Discrete Mathematics 235, 19--27.
	8	Àlvarez, C. and Serna, M. 1999. The proper interval colored graph problem for caterpillar trees. Technical report LSI 99-12-R, Dept. de Llenguatges i Sistemes Informàtics, Univ. Politècnica de Catalunya.
	9	A. Frieze, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.21, October 14-16, 1996
	10	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP -hard problems, Journal of Computer and System Sciences, v.58 n.1, p.193-210, Feb. 1999 [doi>10.1006/jcss.1998.1605]
	11	Assman, S. F., Peck, G. W., Syslo, M. M., and Zak, J. 1981. The bandwidth of caterpillars with hair of lengths 1 and 2. SIAM J. Algebraic and Discrete Meth. 2, 387--393.
	12	Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
	13	Azizoğlu, C. and Eğecioğlu, Ö. 2002. The isoperimetric number and the bisection width of generalized cylinders. Discrete Mathematics. To appear.
	14	R. Balasubramanian , Michael R. Fellows , Venkatesh Raman, An improved fixed-parameter algorithm for vertex cover, Information Processing Letters, v.65 n.3, p.163-168, Feb. 1998 [doi>10.1016/S0020-0190(97)00213-5]
	15	Barnard, S. T., Pothen, A., and Simon, H. 1995. A spectral algorithm for envelope reduction of sparse matrices. Numerical Linear Algebra with Applications 2, 4, 317--334.
	16	Barnard, S. T. and Simon, H. D. 1994. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience 6, 101--107.
	17	Barth, D., Pellegrini, F., Raspaud, A., and Roman, J. 1995. On bandwidth, cutwidth, and quotient graphs. RAIRO Informatique Théorique et Applications. 29, 6, 487--508.
	18	Roberto Battiti , Alan Albert Bertossi, Greedy, Prohibition, and Reactive Heuristics for Graph Partitioning, IEEE Transactions on Computers, v.48 n.4, p.361-385, April 1999 [doi>10.1109/12.762522]
	19	Berger-Wolf, T. Y. and Reingold, E. M. 2002. Index assignment for multichannel communication under failure. IEEE Trans. Inform. Th.
	20	Bernhart, F. and Kainen, P. C. 1979. The book thickness of a graph. Journal of Combinatorial Theory. Series B 27, 3, 320--331.
	21	Jonathan W. Berry , Mark K. Goldberg, Path optimization for graph partitioning problems, Discrete Applied Mathematics, v.90 n.1-3, p.27-50, Jan. 15, 1999 [doi>10.1016/S0166-218X(98)00084-5]
	22	Bezrukov, S. L. 1999. Edge isoperimetric problems on graphs (a survey). In Graph Theory and Combinatorial Biology (Balatonlelle, 1996), L. Lovasz, A. Gyarfas, G. O. H. Katona, A. Recski, and L. Szekely, Eds. János Bolyai Math. Soc., 157--197.
	23	S. L. Bezrukov , J. D. Chavez , L. H. Harper , M. Röttger , U.-P. Schroeder, The congestion of n-cube layout on a rectangular grid, Discrete Mathematics, v.213 n.1-3, p.13-19, Feb. 28 200 [doi>10.1016/S0012-365X(99)00162-4]
	24	Sergej L. Bezrukov , Robert Elsässer , Burkhard Monien , Robert Preis , Jean-Pierre Tillich, New Spectral Lower Bounds on the Bisection Width of Graphs, Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, p.23-34, June 15-17, 2000
	25	Bhatt, S. N. and Leighton, F. T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300--343.
	26	Bilski, T. 1993. Embedding graphs in books with prespecified order of vertices. Poznańskie Towarzystwo Przyjaciól Nauk. Wydzial Nauk Technicznych. Prace Komisji Automatyki i Informatyki. Studia z Automatyki 18, 5--12.
	27	Blache, G., Karpinski, M., and Wirtgen, J. 1998. On approximation intractability of the bandwidth problem. Technical report TR98-014, Electronic Colloquium on Computational Complexity.
	28	Avrim Blum , Goran Konjevod , R. Ravi , Santosh Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, v.235 n.1, p.25-42, March 17, 2000 [doi>10.1016/S0304-3975(99)00181-4]
	29	Hans L. Bodlaender , Michael R. Fellows , Michael T. Hallett, Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.449-458, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195229]
	30	Bodlaender, H. L. 1993. A tourist guide through treewidth. Acta Cybernetica 11, 1-2, 1--21.
	31	Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
	32	Hans L. Bodlaender , Babette de Fluiter, On intervalizing k-colored graphs for DNA physical mapping, Discrete Applied Mathematics, v.71 n.1-3, p.55-77, Dec. 5, 1996 [doi>10.1016/S0166-218X(96)00057-1]
	33	Hans L. Bodlaender , John R. Gilbert , Hjálmtýr Hafsteinsson , Ton Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, v.18 n.2, p.238-255, March 1995 [doi>10.1006/jagm.1995.1009]
	34	Hans L. Bodlaender , Ton Kloks , Dieter Kratsch, Treewidth and Pathwidth of Permutation Graphs, SIAM Journal on Discrete Mathematics, v.8 n.4, p.606-616, Nov. 1995 [doi>10.1137/S089548019223992X]
	35	Hans L. Bodlaender , Rolf H. Möhring, The pathwidth and treewidth of cographs, SIAM Journal on Discrete Mathematics, v.6 n.2, p.181-188, May 1993 [doi>10.1137/0406014]
	36	Bollobás, B. 1985. Random Graphs. Academic Press, London.
	37	Bollobás, B. and Leader, I. 1991. Edge--isoperimetric inequalities in the grid. Combinatorica 4, 299--314.
	38	Boppana, R. 1987. Eigenvalues and graph bisection: An average case analysis. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. 280--285.
	39	Claudson F. Bornstein , Santosh Vempala, Flow Metrics, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.516-527, April 03-06, 2002
	40	Rodrigo A. Botafogo, Cluster analysis for hypertext systems, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.116-125, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160704]
	41	Thang Nguyen Bui , F. Thomson Leighton , Soma Chaudhuri , Michael Sipser, Graph bisection algorithms with good average case behavior, Combinatorica, v.7 n.2, p.171-191, June 1, 1987 [doi>10.1007/BF02579448]
	42	Thang Nguyen Bui , Andrew Peck, Partitioning planar graphs, SIAM Journal on Computing, v.21 n.2, p.203-215, April 1992 [doi>10.1137/0221016]
	43	Caprara, A., Malucelli, F., and Pretolani, D. 2002. On bandwidth-2 graphs. Discrete Applied Mathematics. 117, 1--13.
	44	Ted Carson , Russell Impagliazzo, Hill-climbing finds random planted bisections, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.903-909, January 07-09, 2001, Washington, D.C., United States
	45	Chang, G. J. and Lai, Y.-L. 2001. On the profile of the corona of two graphs. Manuscript (provided by S. Bezrukov).
	46	Chinn, P., Chvátalová, J., Dewdney, A., and Gibbs, N. 1982. The bandwidth problem for graphs and matrices---A survey. Journal of Graph Theory 6, 223--254.
	47	Chinn, P. Z., Lin, Y. X., and Yuan, J. J. 1992. The bandwidth of the corona of two graphs. In Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 91. Utilitas Math., 141--152.
	48	Chinn, P. Z., Lin, Y. X., Yuan, J. J., and Williams, K. 1995. Bandwidth of the composition of certain graph powers. Ars Combinatoria 39, 167--173.
	49	Chirravuri, S., Bhandarkar, S. M., and Arnold, J. 1996. Parallel computing of physical maps---A comparative study in SIMD and MIMD parallelism. Journal of Computational Biology 3, 4, 503--528.
	50	Chung, F. R. K. 1988. Labelings of Graphs. Academic Press, San Diego, 151--168.
	51	Fan R. K. Chung , Frank Thomson Leighton , Arnold L. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design, SIAM Journal on Algebraic and Discrete Methods, v.8 n.1, p.33-58, January 2, 1987 [doi>10.1137/0608002]
	52	Chung, M., Makedon, F., Sudborough, I. H., and Turner, J. 1982. Polynomial time algorithms for the min cut problem on degree restricted trees. In Proceedings of the 23th Annual Symposium on Foundations of Computer Science. 262--271.
	53	Chvátalová, J. 1975. Optimal labelling of a product of two paths. Discrete Mathematics 11, 249--253.
	54	Chvátalová, J., Dewdney, A., Gibbs, N., and Korfhage, R. 1975. The bandwidth problem for graphs---A collection of recent results. Technical report CS 75020, Dept. of Computer Science, Southern Methodist University.
	55	Anne Condon , Richard M. Karp, Algorithms for graph partitioning on the planted partition model, Random Structures & Algorithms, v.18 n.2, p.116-140, March 1,2001 [doi>10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2]
	56	Pierluigi Crescenzi, On weighted vs unweighted versions of combinatorial optimizationproblems, Information and Computation, v.167 n.1, p.10-26, 5/25/2001 [doi>10.1006/inco.2000.3011]
	57	E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
	58	Deo, N., Krishnamoorthy, M. S., and Langston, M. A. 1987. Exact and approximate solutions for the gate matrix layout problem. IEEE Transactions on Computer Aided Design 6, 1, 79--84.
	59	Dewdney, A. K. 1976. The bandwidth of a graph---some recent results. In Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing. Number 17 in Congressus Numerantium. Utilitas Math., 273--288.
	60	Díaz, J. 1979. The Δ-operator. In Fundamentals of Computation Theory, L. Budach, Ed. Akademie--Verlag, 105--111.
	61	Josep Díaz, Graph Layout Problems, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.14-23, August 24-28, 1992
	62	Josep Díaz , Alan Gibbons , Grammati E. Pantziou , Maria J. Serna , Paul G. Spirakis , Jacobo Toran, Parallel algorithms for the minimum cut and the minimum length tree layout problems, Theoretical Computer Science, v.181 n.2, p.267-287, July 30, 1997 [doi>10.1016/S0304-3975(96)00274-5]
	63	Díaz, J., Gibbons, A. M., Paterson, M. S., and Torán, J. 1991. The Minsumcut problem. In Algorithms and Data Structures, F. Dehen, R. J. Sack, and N. Santoro, Eds. Lecture Notes in Computer Science, vol. 519. Springer-Verlag, 65--79.
	64	Josep Díaz , Mathew D. Penrose , Jordi Petit , María Serna, Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs, Combinatorics, Probability and Computing, v.9 n.6, p.489-511, November 2000 [doi>10.1017/S0963548300004454]
	65	Joseph Díz , Mathew D. Penrose , Jordi Petit , María Serna, Approximating layout problems on random geometric graphs, Journal of Algorithms, v.39 n.1, p.78-116, April 2001 [doi>10.1006/jagm.2000.1149]
	66	Díaz, J., Petit, J., and Serna, M. 2001b. Faulty random geometric networks. Parallel Processing Letters 10, 4, 343--357.
	67	Díaz, J., Petit, J., Serna, M., and Trevisan, L. 2001c. Approximating layout problems on random graphs. Discrete Mathematics 235, 1--3, 245--253.
	68	Josep Díaz , Maria J. Serna , Paul Spirakis , Jacobo Torán, Paradigms for fast parallel approximability, Cambridge University Press, New York, NY, 1997
	69	Burkhard Monien , Ralf Diekmann , Reinhard Lüling, Communication Throughput of Interconnection Networks, Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994, p.72-86, August 22-26, 1994
	70	Diekmann, R., Lüling, R., Monien, B., and Spräner, C. 1996. Combining helpful sets and parallel simulated annealing for the graph-partitioning problem. Parallel Algorithms and Applications 8, 61--84.
	71	Diekmann, R., Monien, B., and Preis, R. 1995. Using helpful sets to improve graph bisections. In Interconnection Networks and Mapping and Scheduling Parallel Computations, D. F. Hsu, A. L. Rosenberg, and D. Sotteau, Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS Press, 57--73.
	72	Krzystof Diks , Hristo N. Djidjev , Ondrej Sýkora , Imrich Vrťo, Edge separators of planar and outerplanar graphs with applications, Journal of Algorithms, v.14 n.2, p.258-279, March 1993 [doi>10.1006/jagm.1993.1013]
	73	Guoli Ding , Bogdan Oporowski, Some results on tree decomposition of graphs, Journal of Graph Theory, v.20 n.4, p.481-499, Dec. 1995 [doi>10.1002/jgt.3190200412]
	74	Michael John Dinneen , Michael R. Fellows, Bounded combinatorial width and forbidden substructures, 1996
	75	Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995 [doi>10.1016/0304-3975(94)00097-3]
	76	Downey, R. G. and Fellows, M. R. 1999. Parameterized Complexity. Springer-Verlag, New York.
	77	John Dunagan , Santosh Vempala, On Euclidean Embeddings and Bandwidth Minimization, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.229-240, August 18-20, 2001
	78	J. A. Ellis , I. H. Sudborough , J. S. Turner, The vertex separation and search number of a graph, Information and Computation, v.113 n.1, p.50-79, Aug. 15, 1994 [doi>10.1006/inco.1994.1064]
	79	Elsner, U. 1997. Graph partitioning---A survey. Technical Report 393, Technische Universitat Chemnitz.
	80	Guy Even, Fast Approximate Graph Partitioning Algorithms, SIAM Journal on Computing, v.28 n.6, p.2187-2214, Dec. 1999 [doi>10.1137/S0097539796308217]
	81	Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
	82	Even, S. and Itai, A. 1971. Queues, stacks, and graphs. In Theory of Machines and Computations. Academic Press, 71--86.
	83	Even, S. and Shiloach, Y. 1975. NP-completeness of several arrangement problems. Technical Report TR-43, Dept. of Computer Science, Technion, Haifa.
	84	Everstine, G. C. 1979. A comparison of three resequencing algorithms for the reduction of matrix profile and wavefront. Int. J. Num. Meth. Eng. 14, 837--853.
	85	Uriel Feige, Approximating the bandwidth via volume respecting embeddings, Journal of Computer and System Sciences, v.60 n.3, p.510-539, June 2000 [doi>10.1006/jcss.1999.1682]
	86	Feige, U. and Krauthgamer, R. 1998. Improved performance guarantees for bandwidth minimization heuristics (draft). Technical Report, Computer Science Dept., Weizmann Inst. Tech.
	87	Uriel Feige , Robert Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, SIAM Journal on Computing, v.31 n.4, p.1090-1118, 2002 [doi>10.1137/S0097539701387660]
	88	Feige, U., Krauthgamer, R., and Nissim, K. 2002. Approximating the minimum bisection size. Discrete Applied Mathematics.
	89	Michael R. Fellows , Michael T. Hallett , Harold T. Wareham, DNA Physical Mapping: Three Ways Difficult, Proceedings of the First Annual European Symposium on Algorithms, p.157-168, September 30-October 02, 1993
	90	Michael R. Fellows , Michael A. Langston, Layout permutation problems and well-partially-ordered sets, Proceedings of the fifth MIT conference on Advanced research in VLSI, p.315-327, January 1988, Cambridge, Massachusetts, United States
	91	Michael R. Fellows , Michael A. Langston, On well-partial-order theory and its application to combinatorial problems of VLSI design, SIAM Journal on Discrete Mathematics, v.5 n.1, p.117-126, Feb. 1992 [doi>10.1137/0405010]
	92	Michael R. Fellows , Michael A. Langston, On search, decision, and the efficiency of polynomial-time algorithms, Journal of Computer and System Sciences, v.49 n.3, p.769-779, Dec. 1994
	93	Peter Fishburn , Prasad Tetali , Peter Winkler, Optimal linear arrangement of a rectangular grid, Discrete Mathematics, v.213 n.1-3, p.123-139, Feb. 28 200 [doi>10.1016/S0012-365X(99)00173-9]
	94	Ford, L. R. and Fulkerson, D. R. 1962. Flows in Networks. Princeton University Press.
	95	A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
	96	Gallian, J. 1998. A dynamic survey of graph labeling. Electronic Journal of Combininatorics 5, 1.
	97	Garey, M. R., Graham, R. L., Johnson, D. S., and Knuth, D. 1978. Complexity results for bandwidth minimization. SIAM J. Appl. Mathem. 34, 477--495.
	98	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	99	Garey, M. R., Johnson, D. S., Miller, G. L., and Papadimitriou, C. H. 1980. The complexity of coloring circular arcs and chords. SIAM J. Algeb. Discrete Meth. 1, 2, 216--227.
	100	Garey, M. R., Johnson, D. S., and Stockmeyer, L. 1976. Some simplified NP-complete graph problems. Theoretical Computer Science 1, 237--267.
	101	Gavril, F. 1977. Some NP-complete problems on graphs. In 11th Conference on Information Sciences and Systems. John Hopkins University, Baltimore, 91--95.
	102	Gibbs, N. E., Poole, Jr., W. G., and Stockmeyer, P. K. 1976. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM J. Num. Anal. 13, 2, 236--250.
	103	Fred Glover , Fred Laguna, Tabu Search, Kluwer Academic Publishers, Norwell, MA, 1997
	104	Goldberg, M. and Miller, Z. 1988. A parallel algorithm for bisection width in trees. Computers & Mathematics with Applications 15, 4, 259--266.
	105	Goldberg, M. K. and Klipker, I. A. 1976. An algorithm for minimal numeration of tree vertices. Sakharth. SSR Mecn. Akad. Moambe 81, 3, 553--556. In Russian.
	106	Goldberg, P. W., Golumbic, M. C., Kaplan, H., and Shamir, R. 1995. Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 1, 139--152.
	107	Golovach, P. A. 1997. The total vertex separation number of a graph. Diskretnaya Matematika 9, 4, 86--91. In Russian.
	108	Golovach, P. A. and Fomin, F. V. 1998. The total vertex separation number and the profile of graphs. Diskretnaya Matematika 10, 1, 87--94. In Russian.
	109	Golumbic, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.
	110	Martin Charles Golumbic , Haim Kaplan , Ron Shamir, On the complexity of DNA physical mapping, Advances in Applied Mathematics, v.15 n.3, p.251-261, Sept. 1994 [doi>10.1006/aama.1994.1009]
	111	Martin Charles Golumbic , Haim Kaplan , Ron Shamir, Graph sandwich problems, Journal of Algorithms, v.19 n.3, p.449-473, Nov. 1995 [doi>10.1006/jagm.1995.1047]
	112	Martin Charles Golumbic , Ron Shamir, Complexity and algorithms for reasoning about time: a graph-theoretic approach, Journal of the ACM (JACM), v.40 n.5, p.1108-1133, Nov. 1993 [doi>10.1145/174147.169675]
	113	Gomory, R. E. and Hu, T. C. 1975. Multi-Terminal Flows in a Network. Studies in Mathematics, vol. 11. MAA, 172--199.
	114	Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo, Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, 1995
	115	Grimmett, G. R. 1999. Percolation, second ed. Springer-Verlag, Heidelberg.
	116	Anupam Gupta, Improved bandwidth approximation for trees and chordal graphs, Journal of Algorithms, v.40 n.1, p.24-36, July 2001 [doi>10.1006/jagm.2000.1118]
	117	Gurari, E. and Sudborough, I. H. 1984. Improved dynamic programming algorithms for the bandwidth minimization and the mincut linear arrangement problem. J. Algor. 5, 531--546.
	118	Jens Gustedt, On the pathwidth of chordal graphs, Discrete Applied Mathematics, v.45 n.3, p.233-248, Sept. 7, 1993 [doi>10.1016/0166-218X(93)90012-D]
	119	William W. Hager, Minimizing the Profile of a Symmetric Matrix, SIAM Journal on Scientific Computing, v.23 n.5, p.1799-1816, 2002 [doi>10.1137/S1064827500379215]
	120	Hansen, M. D. 1989. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In 30th Annual Symposium on Foundations of Computer Science. 604--609.
	121	Haralambides, J. and Makedon, F. 1997. Approximation algorithms for the bandwidth minimization problem for a large class of trees. Theory of Computing Systems 30, 67--90.
	122	Haralambides, J., Makedon, F., and Monien, B. 1991. Bandwidth minimization: an approximation algorithm for caterpillars. Mathematical Systems Theory 24, 169--177.
	123	Harary, F. 1967. Problem 16. In Graph Theory and Computing, M. Fiedler, Ed. Czechoslovak Academy Sciences, 161.
	124	Harper, L. H. 1964. Optimal assignments of numbers to vertices. J. SIAM 12, 1, 131--135.
	125	Harper, L. H. 1966. Optimal numberings and isoperimetric problems on graphs. J. Combinatorial Theory 1, 3, 385--393.
	126	Harper, L. H. 1970. Chassis layout and isoperimetric problems. Technical Report SPS 37--66, vol II, Jet Propulsion Laboratory.
	127	Harper, L. H. 1977. Stabilization and the edgesum problem. Ars Combinatoria 4, 225--270.
	128	Harper, L. H. 2001. On the bandwidth of a hamming graph. Manuscript.
	129	Lenwood S. Heath , Frank Thomson Leighton , Arnold L. Rosenberg, Comparing queues and stacks as mechanisms for laying out graphs, SIAM Journal on Discrete Mathematics, v.5 n.3, p.398-412, Aug. 1992 [doi>10.1137/0405031]
	130	Lenwood S. Heath , Sriram V. Pemmaraju, Stack and Queue Layouts of Posets, SIAM Journal on Discrete Mathematics, v.10 n.4, p.599-625, 1997 [doi>10.1137/S0895480193252380]
	131	Lenwood S. Heath , Sriram V. Pemmaraju, Stack and Queue Layouts of Directed Acyclic Graphs: Part II, SIAM Journal on Computing, v.28 n.5, p.1588-1626, April/May 1999 [doi>10.1137/S0097539795291550]
	132	Heath, L. S., Pemmaraju, S. V., and Ribbens, C. J. 1993. Sparse Matrix-Vector Multiplication on a Small Linear Array. Springer-Verlag.
	133	Lenwood S. Heath , Sriram V. Pemmaraju , Ann N. Trenk, Stack and Queue Layouts of Directed Acyclic Graphs: Part I, SIAM Journal on Computing, v.28 n.4, p.1510-1539, Aug. 1999 [doi>10.1137/S0097539795280287]
	134	Lenwood S. Heath , Arnold L. Rosenberg, Laying out graphs using queues, SIAM Journal on Computing, v.21 n.5, p.927-958, Oct. 1992 [doi>10.1137/0221055]
	135	Ralf Heckmann , Ralf Klasing , Burkhard Monien , Walter Unger, Optimal embedding of complete binary trees into lines and grids, Journal of Parallel and Distributed Computing, v.49 n.1, p.40-56, Feb. 1998 [doi>10.1006/jpdc.1998.1424]
	136	Helmberg, C., Rendl, F., Mohar, B., and Poljak, S. 1995. A spectral approach to bandwidth and separator problems in graphs. Linear and Multilinear Algebra 39, 1-2, 73--90.
	137	U. Hendrich , M. Stiebitz, On the bandwidth of graph products, Journal of Information Processing and Cybernetics, v.28 n.3, p.113-125, 1992
	138	Hendrickson, B. and Leland, R. 1997. The Chaco user's guide: version 2.0. Technical Report SAND94--2692, Sandia National Laboratories. ftp://ftp.cs.sandia.gov/pub/papers/bahendr/guide.ps.gz.
	139	Hromkovi&cbreve;, J. and Monien, B. 1992. The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems). Teubner, Stuttgart, 215--233.
	140	Hu, T. C. 1974. Optimum communication spanning trees. SIAM J. Comput. 3, 188--195.
	141	Janson, S., Luczak, T., and Rucinski, A. 2000. Random Graphs. Wiley, New York.
	142	Mark Jerrum , Gregory B. Sorkin, The metropolis algorithm for graph bisection, Discrete Applied Mathematics, v.82 n.1-3, p.155-175, March 2, 1998 [doi>10.1016/S0166-218X(97)00133-9]
	143	David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning, Operations Research, v.37 n.6, p.865-892, Nov–Dec. 1989 [doi>10.1287/opre.37.6.865]
	144	Johnson, D. S., Lenstra, J. K., and Kan, A. H. G. R. 1978. The complexity of the network design problem. Networks 8, 4, 279--285.
	145	Ari Juels , Alistair Sinclair, Topics in black-box combinatorial optimization, 1996
	146	Martin Juvan , Bojan Mohar, Optimal linear labelings and eigenvalues of graphs, Discrete Applied Mathematics, v.36 n.2, p.153-168, April 30, 1992 [doi>10.1016/0166-218X(92)90229-4]
	147	Kadluczka, P. and Wala, K. 1995. Tabu search and genetic algorithms for the generalized graph partitioning problem. Control and Cybernetics 24, 4, 459--476.
	148	Haim Kaplan , Ron Shamir, Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques, SIAM Journal on Computing, v.25 n.3, p.540-561, June 1996 [doi>10.1137/S0097539793258143]
	149	Kaplan, H. and Shamir, R. 1999. Bounded degree interval sandwich problems. Algorithmica 24, 2, 96--104.
	150	Haim Kaplan , Ron Shamir , Robert E. Tarjan, Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs, SIAM Journal on Computing, v.28 n.5, p.1906-1922, April/May 1999 [doi>10.1137/S0097539796303044]
	151	David R. Karger, A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem, SIAM Journal on Computing, v.29 n.2, p.492-514, Oct. 1999 [doi>10.1137/S0097539796298340]
	152	Richard M. Karp, Mapping the genome: some combinatorial problems arising in molecular biology, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.278-285, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167170]
	153	Karpinski, M., Wirtgen, J., and Zelikovsky, A. 1997. An approximating algorithm for the bandwidth problem on dense graphs. Technical Report TR 97-017, Electronic Colloquium on Computational Complexity.
	154	Karypis, G. 2001. Metis's home page. Web page. http://www-users.cs.umn.edu/∼karypis/metis.
	155	Kendall, D. G. 1969. Incidence matrices, interval graphs, and seriation in archeology. Pacific J. Mathem. 28, 565--570.
	156	Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49, 291--307.
	157	King, I. P. 1970. An automatic reordering schema for simultaneous equations derived from network system. Int. J. Numer. Meth. Eng. 2, 523--533.
	158	Nancy G. Kinnersley, The vertex separation number of a graph equals its path-width, Information Processing Letters, v.42 n.6, p.345-350, July 24, 1992 [doi>10.1016/0020-0190(92)90234-M]
	159	M Kirousis , C H Papadimitriou, Searching and pebbling, Theoretical Computer Science, v.47 n.2, p.205-218, Nov. 1986
	160	Ralf Klasing, The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width, Discrete Applied Mathematics, v.83 n.1-3, p.229-246, March 25, 1998 [doi>10.1016/S0166-218X(97)00112-1]
	161	G. B. Khosrovshahi , S. Ajoodani-Namini, Computing the bandwidth of interval graphs, SIAM Journal on Discrete Mathematics, v.3 n.3, p.373-375, Aug. 1990 [doi>10.1137/0403033]
	162	Ton Kloks , Dieter Kratsch , Haiko Muüller, Bandwidth of chain graphs, Information Processing Letters, v.68 n.6, p.313-315, Dec 1998 [doi>10.1016/S0020-0190(98)00173-2]
	163	Kloks, T., Kratsch, D., and Müller, H. 1999. Approximating the bandwidth for asteroidal triple-free graphs. J. Algor. 32, 1, 41--57.
	164	Dieter Kratsch, Finding the minimum bandwidth of an interval graph, Information and Computation, v.74 n.2, p.140-158, Aug. 1987 [doi>10.1016/0890-5401(87)90028-9]
	165	Kumfert, G. and Pothen, A. 1997. Two improved algorithms for reducing the envelope and wavefront. BIT 37, 3, 001--032.
	166	David Kuo , Gerard J. Chang, The Profile Minimization Problem in Trees, SIAM Journal on Computing, v.23 n.1, p.71-81, Feb. 1994 [doi>10.1137/S009753979119607X]
	167	Yung-Ling Lai, Bandwidth, edgesum and profile of graphs, Western Michigan University, Kalamazoo, MI, 1997
	168	Lai, Y.-L. 2001. On the profile of the tensor product of path with complete bipartite graphs. Manuscript (provided by S. Bezrukov).
	169	Lai, Y.-L., Liu, J., and Williams, K. 1994. Bandwidth for the sum of k graphs. Ars Combinatoria 37, 149--155.
	170	Lai, Y.-L. and Williams, K. 1994. The edgesum of the sum of k sum deterministic graphs. In Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. 102. Utilitas Math., 231--236.
	171	Lai, Y.-L. and Williams, K. 1995. Bandwidth of the strong product of paths and cycles. In Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. 109. Utilitas Math., 123--128.
	172	Yung-Ling Lai , Kenneth Williams, On bandwidth for the tensor product of paths and cycles, Discrete Applied Mathematics, v.73 n.2, p.133-141, March 1997 [doi>10.1016/S0166-218X(95)00005-C]
	173	Lai, Y.-L. and Williams, K. 1999. A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31, 2, 75--94.
	174	Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
	175	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	176	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
	177	Leiserson, C. E. 1980. Area-efficient graph layouts (for VLSI). In Proceedings of the 21st Annual Symposium on Foundations of Computer Science. 270--281.
	178	Leland, R. and Hendrickson, B. 1994. An empirical study of static load balancing algorithms. In Scalable High-Performance Computing Conference. IEEE Computer Society Press, 682--685.
	179	Lengauer, T. 1981. Black-white pebbles and graph separation. Acta Informatica 16, 465--475.
	180	Lengauer, T. 1982. Upper and lower bounds on the complexity of the min-cut linear arrangements problem on trees. SIAM J. Algeb. Discrete Meth. 3, 99--113.
	181	Lepin, V. V. 1986. Profile minimization problem of matrices and graphs. Academy of Sciences of Belarus. Institute of Mathematics. 33, 269. In Russian.
	182	Lewis, R. 1994. Simulated annealing for profile and fill reduction of sparse matrices. Int. J. Num. Meth. Eng. 37, 6.
	183	Lin, Y. X. 1994. Two-dimensional bandwidth problem. In Combinatorics, Graph Theory, Algorithms and Applications (Beijing, 1993). World Sci. Publishing, 223--232.
	184	Lin, Y. X. and Yuan, J. 1994a. Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica. English Series 10, 1, 107--112.
	185	Lin, Y. X. and Yuan, J. J. 1994b. Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica. English Series. Yingyong Shuxue Xuebao 10, 1, 107--112.
	186	Lindsey, J. H. 1964. Assignments of numbers to vertices. American Mathematical Monthly 71, 508--516.
	187	Lipton, R. J. and Tarjan, R. E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Mathem. 36, 177--189.
	188	Liu, H. E. and Yuan, J. J. 1995. The cutwidth problem for graphs. Gaoxiao Yingyong Shuxue Xuebao. Applied Mathematics. A Journal of Chinese Universities. Series A 10, 3, 339--348. In Chinese.
	189	Liu, J. 1992. On bandwidth sum for the composition of paths and cycles. Technical Report Rep/92-06, Dept. of Computer Science, Western Michigan Univ.
	190	Jiuqiang Liu , Kenneth Williams, On bandwidth and edgesum for the composition of two graphs, Discrete Mathematics, v.143 n.1-3, p.159-166, Aug. 16, 1995 [doi>10.1016/0012-365X(94)00013-9]
	191	Malwina J. Luczak , Colin McDiarmid, Bisecting sparse random graphs, Random Structures & Algorithms, v.18 n.1, p.31-38, Jan. 2001 [doi>10.1002/1098-2418(200101)18:1<31::AID-RSA3>3.0.CO;2-1]
	192	Robert Malcolm Macgregor, On partitioning a graph: a theoretical and empirical study., 1978
	193	R. Mahesh , C. Pandu Rangan , Aravind Srinivasan, On finding the minimum bandwidth of interval graphs, Information and Computation, v.95 n.2, p.218-224, Dec. 1991 [doi>10.1016/0890-5401(91)90045-4]
	194	Mai, J. H. 1996. Profiles of some classes of condensable graphs. J. Syst. Sci. Mathem. Sci. Xitong Kexue yu Shuxue 16, 2, 141--148.
	195	Mai, J. H. and Luo, H. P. 1984. Some theorems on the bandwidth of a graph. Acta Mathematicae Applicatae Sinica. Yingyong Shuxue Xuebao 7, 1, 86--95.
	196	Makedon, F., Papadimitriou, C. H., and Sudborough, I. H. 1985. Topological bandwidth. SIAM J. Algeb. Discrete Meth. 6, 3, 418--444.
	197	Fillia Makedon , Dafna Sheinwald , Yaron Wolfsthal, A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs, Information Processing Letters, v.46 n.2, p.103-107, May 17, 1993 [doi>10.1016/0020-0190(93)90206-O]
	198	Fillia Makedon , Ivan Hal Sudborough, On minimizing width in linear layouts, Discrete Applied Mathematics, v.23 n.3, p.243-265, June 1989 [doi>10.1016/0166-218X(89)90016-4]
	199	Manabe, Y., Hagihara, K., and Tokura, N. 1984. The minimum bisection widths of the cube-connected cycles graph and cube graph. Systems-Computers-Controls. The Transactions of the Institute of Electronics and Communication Engineers of Japan 15, 6, 9--18.
	200	Miller, Z. 1991. Multidimensional bandwidth in random graphs. In Graph Theory, Combinatorics, and Applications. Vol. 2 (Kalamazoo, MI, 1988). Wiley, New York, 861--870.
	201	Graeme Mitchison , Richard Durbin, Optimal numberings of an N N array, SIAM Journal on Algebraic and Discrete Methods, v.7 n.4, p.571-582, Oct. 1986 [doi>10.1137/0607063]
	202	Mohar, B. and Poljak, S. 1993. Eigenvalues in combinatorial optimization. In Combinatorial and Graph-Theoretical Problems in Linear Algebra, R. A. Brualdi, S. Friedland, and V. Klee, Eds. IMA Volumes in Mathematics and its Applications, vol. 50. Springer-Verlag, 107--151.
	203	Burkhard Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete, SIAM Journal on Algebraic and Discrete Methods, v.7 n.4, p.505-512, Oct. 1986 [doi>10.1137/0607057]
	204	B. Monien , I. H. Sudborough, Min cut is NP-complete for edge weighted trees, Theoretical Computer Science, v.58 n.1-3, p.209-229, June 1988 [doi>10.1016/0304-3975(88)90028-X]
	205	Monien, B. and Sudborough, I. H. 1990. Embedding one interconnection network in another. In Computational Graph Theory, G. Tinhofer, E. Mayr, H. Noltemeier, and M. M. Syslo, Eds. Computing Supplementa, vol. 7. Springer-Verlag, 257--282.
	206	Muradyan, D. 1999. Proceedings of Computer Science & Information Technologies Conference, Armenia.
	207	Muradyan, D. O. 1982. Minimal numberings of a two-dimensional cylinder. Akademiya Nauk Armyanskoĭ SSR. Doklady 75, 3, 114--119. In Russian.
	208	Muradyan, D. O. 1985. Some estimates for the length of an arbitrary graph. Mat. Voprosy Kibernet. Vychisl. Tekhn.14, 79--86, 126. In Russian.
	209	Muradyan, D. O. 1986. A polynomial algorithm for finding the bandwidth of interval graphs. Akademiya Nauk Armyanskoĭ SSR. Doklady 82, 2, 64--66. In Russian.
	210	Muradyan, D. O. and Piliposyan, T. E. 1980. Minimal numberings of vertices of a rectangular lattice. Akad. Nauk. Armjan. SRR 1, 70, 21--27. In Russian.
	211	Muradyan, D. O. and Piliposyan, T. E. 1980. The problem of finding the length and width of the complete p-partite graph. Uchen. Zapiski Erevan. Gosunivers. 2, 18--26. In Russian.
	212	Petra Mutzel, A Polyhedral Approach to Planar Augmentation and Related Problems, Proceedings of the Third Annual European Symposium on Algorithms, p.494-507, September 25-27, 1995
	213	Koji Nakano, Linear Layouts of Generalized Hypercubes, Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, p.364-375, June 16-18, 1993
	214	Niepel, L. and Tomasta, P. 1981. Elevation of a graph. Czechoslovak Mathematical Journal 31(106), 3, 475--483.
	215	Papadimitriou, C. 1976. The NP-completeness of the bandwidth minimization problem. Computing 16, 263--270.
	216	Papadimitriou, C. H. and Sideri, M. 1996. The bisection width of grid graphs. Mathematical Systems Theory 29, 2, 97--110.
	217	Mathew D. Penrose, Single linkage clustering and continuum percolation, Journal of Multivariate Analysis, v.53 n.1, p.94-109, April 1995 [doi>10.1006/jmva.1995.1026]
	218	Penrose, M. 2000. Vertex ordering and partitioning problems for random spatial graphs. The Annals of Applied Probability 10, 517--538.
	219	Petit, J. 1998. Approximation heuristics and benchmarkings for the MinLA problem. In Alex '98---Building Bridges Between Theory and Applications, R. Battiti and A. Bertossi, Eds. 112--128.
	220	Petit, J. 2000. Combining spectral sequencing and parallel simulated annealing for the minLA problem. Technical Report LSI-01-13-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya.
	221	Petit, J. 2001a. Experiments for the MinLAP problem. Technical Report LSI-R01-7-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya.
	222	Petit, J. 2001b. Layout problems. Ph.D. thesis, Universitat Politècnica de Catalunya.
	223	Preis, R. and Diekmann, R. 1996. The Party partitioning library user guide. Technical Report TR-RSFB-96-024, Universität Paderborn.
	224	Satish Rao , Andréa W. Richa, New approximation techniques for some ordering problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.211-218, January 25-27, 1998, San Francisco, California, United States
	225	Raspaud, A., Sýkora, O., and Vr&tbreve;o, I. 1995. Cutwidth of the de Bruijn graph. RAIRO Informatique Théorique et Applications 29, 6, 509--514.
	226	Raspaud, A., Sýkora, O., and Vr&tbreve;o, I. 2000. Congestion and dilation, similarities and differences---a survey. In Proceedings 7th International Colloquium on Structural Information and Communication Complexity. Carleton Scientific, 269--280.
	227	R. Ravi , Ajit Agrawal , Philip Klein, Ordering problems approximated: single-processor scheduling and interval graph completion, Proceedings of the 18th international colloquium on Automata, languages and programming, p.751-762, June 1991, Madrid, Spain
	228	Robertson, N. and Seymour, P. D. 1985. Graph minors---a survey. In Surveys in Combinatorics. Cambridge University Press, 153--171.
	229	José D. P. Rolim , Ondrej Sýkora , Imrich Vrto, Optimal Cutwidths and Bisection Widths of 2- and 3-Dimensional Meshes, Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, p.252-264, June 20-22, 1995
	230	José Rolim , Pavel Tvrdík , Jan Trdlička , Imrich Vrt'o, Bisecting de Bruijn and Kautz graphs, Discrete Applied Mathematics, v.85 n.1, p.87-97, June 1, 1998 [doi>10.1016/S0166-218X(98)00031-6]
	231	Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
	232	Saxe, J. B. 1980. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algeb. Discrete Meth. 1, 4, 363--369.
	233	Seymour, P. D. 1995. Packing directed circuits fractionally. Combinatorica 15, 2, 281--288.
	234	Seymour, P. D. and Thomas, R. 1994. Call routing and the ratcatcher. Combinatorica 14, 2, 217--241.
	235	Shahrokhi, F., Sýkora, O., Székely, L. A., and Vr&tbreve;o, I. 1997. Crossing numbers: bounds and applications. János Bolyai Math. Soc., Budapest, 179--206.
	236	Farhad Shahrokhi , Ondrej Sýkora , László A. Székely , Imrich Vrto, On Bipartite Drawings and the Linear Arrangement Problem, SIAM Journal on Computing, v.30 n.6, p.1773-1789, 2001 [doi>10.1137/S0097539797331671]
	237	Shiloach, Y. 1979. A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 8, 1, 15--32.
	238	Shing, M. T. and Hu, T. C. 1986. Computational complexity of layout problems. In Layout Design and Verification, T. Ohtsuki, Ed. Advances in CAD for VLSI, vol. 4. North--Holland, Amsterdam, 267--294.
	239	Horst D. Simon , Shang-Hua Teng, How Good is Recursive Bisection?, SIAM Journal on Scientific Computing, v.18 n.5, p.1436-1445, Sept. 1997 [doi>10.1137/S1064827593255135]
	240	Konstantin Skodinis, Computing Optimal Linear Layouts of Trees in Linear Time, Proceedings of the 8th Annual European Symposium on Algorithms, p.403-414, September 05-08, 2000
	241	Soumyanath, K. and Deogun, J. S. 1990. On the bisection width of partial k-trees. In Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 74. Utilitas Math., 25--37.
	242	D. A. Spielmat, Spectral partitioning works: planar graphs and finite element meshes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.96, October 14-16, 1996
	243	Alan P. Sprague, An $0(n \log n)$ Algorithm for Bandwidth of Interval Graphs, SIAM Journal on Discrete Mathematics, v.7 n.2, p.213-220, May 1994 [doi>10.1137/S0895480192232333]
	244	Ladislav Stacho , Imrich Vrt'o, Bisection width of transposition graphs, Discrete Applied Mathematics, v.84 n.1-3, p.221-235, May 15, 1998 [doi>10.1016/S0166-218X(98)00009-2]
	245	Ondrej Sýkora , Imrich Vrťo, Edge separators for graphs of bounded genus with applications, Theoretical Computer Science, v.112 n.2, p.419-429, May 10, 1993 [doi>10.1016/0304-3975(93)90031-N]
	246	Tewarson, R. 1973. Sparse Matrices. Academic Press, New York.
	247	Dimitrios M. Thilikos , Maria J. Serna , Hans L. Bodlaender, Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width, Proceedings of the 11th International Conference on Algorithms and Computation, p.192-203, December 18-20, 2000
	248	Dimitrios M. Thilikos , Maria J. Serna , Hans L. Bodlaender, A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth, Proceedings of the 9th Annual European Symposium on Algorithms, p.380-390, August 28-31, 2001
	249	C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
	250	Jonathan S Turner, On the probable performance of Heuristics for bandwidth minimization, SIAM Journal on Computing, v.15 n.2, p.561-580, May 1986 [doi>10.1137/0215041]
	251	Walter Unger, The Complexity of the Approximation of the Bandwidth Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.82, November 08-11, 1998
	252	Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
	253	Vr&tbreve;o, I. 2000. Cutwidth of the r-dimensional mesh of d-ary trees. RAIRO Informatique Théorique et Applications 34, 6, 515--519.
	254	Vr&tbreve;o, I. 2002. Crossing numbers of graphs: A bibliography. ftp://ftp.ifi.savba.sk/pub/imrich/crobib.ps.gz.
	255	Williams, K. 1993. On the minimum sum of the corona of two graphs. In Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 94. Utilitas Math., 43--49.
	256	Williams, K. 1994. On bandwidth and edgesum for the tensor product of paths with complete bipartite graphs. In Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. 102. Utilitas Math., 183--190.
	257	Williams, K. 1996. On bandwidth for the tensor product of paths and cycles with complete graphs. Bulletin of the Institute of Combinatorics and its Applications 16, 41--48.
	258	Bang Ye Wu , Giuseppe Lancia , Vineet Bafna , Kun-Mao Chao , R. Ravi , Chuan Yi Tang, A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees, SIAM Journal on Computing, v.29 n.3, p.761-778, Dec. 1999 to Jan. 2000 [doi>10.1137/S009753979732253X]
	259	Mihalis Yannakakis, A polynomial algorithm for the min-cut linear arrangement of trees, Journal of the ACM (JACM), v.32 n.4, p.950-988, Oct. 1985 [doi>10.1145/4221.4228]
	260	Yuan, J., Lin, Y., Liu, Y., and Wang, S. 1998. NP-completeness of the profile problem and the fill-in problem on cobipartite graphs. J. Mathem. Study 31, 3, 239--243.
	261	Sanming Zhou , Jinjiang Yuan, Harper-type lower bounds and the bandwidths of the compositions of graphs, Discrete Mathematics, v.181 n.1-3, p.255-266, Feb. 15, 1998 [doi>10.1016/S0012-365X(97)00040-X]