zbMATH — the first resource for mathematics

A variation on the min cut linear arrangement problem. (English) Zbl 0643.68094
Summary: The min cut linear arrangement problem asks, for a given graph G and a positive integer k, if there exists a linear arrangement of G’s vertices so that any line separating consecutive vertices in the layout cuts at most k of the edges. A variation of this problem insists that the arrangement be made on a (fixed-degree) tree instead of a line. We show that (1) this problem is NP-complete even when G is planar; (2) it is easily solved when G is a tree; and (3) there is a simple characterization for all graphs with cost 2 or less. Our main result is a linear-time algorithm to embed an outerplanar graph G into a spanning tree with cost at most max degree(G)\(+1\). This result is important because it extends to an approximation algorithm for the standard min cut linear arrangement problem on outerplanar graphs.

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Adolphson, D. and Hu, T. C., Optimal Linear Ordering,SIAM J. Appl. Math. 25, 3 (1973), pp. 403–423. · Zbl 0274.90061 · doi:10.1137/0125042
[2] Baker, B., Approximation Algorithms forNP-complete Problems on Planar Graphs, Manuscript, Bell Laboratories, Murray Hill, New Jersey (1983).
[3] Berge, C.,Graphs and Hypergraphs, North-Holland, Amsterdam (1973).
[4] Bhatt, S., Chung, F., Leighton, T., and Rosenberg, A., Optimal Simulations of Tree Machines,Proc. 27th IEEE Foundations of Computer Science Symp. (1986), pp. 274–282.
[5] Chung, F. R. K., On Optimal Linear Arrangement of Trees,Comput. Math. Appl. 10, 1 (1984), pp. 43–60. · Zbl 0533.05022 · doi:10.1016/0898-1221(84)90085-3
[6] Ellis, J., Sudborough, I. H., and Turner, J., Graph Separation and Search Number,Proc. 1983 Allerton Conf. on Communications, Control and Computing (1983).
[7] Garey, M. R., Graham, R. L., Johnson, D. S., and Knuth, D. E., Complexity Results for Bandwidth Minimization,SIAM J. Appl. Math. 34 (1978), pp. 477–495. · Zbl 0385.05048 · doi:10.1137/0134037
[8] Garey, M. R., and Johnson, D. S.,Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco (1979). · Zbl 0411.68039
[9] Garey, M. R., Johnson, D. S., and Stockmeyer, L. J., Some SimplifiedNP-complete Graph Problems,Theort. Comput. Sci. 1 (1976), pp. 237–267. · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[10] Hong, J. W., Mehlhorn, K., and Rosenberg, A. L., Cost Trade-offs in Graph Embeddings with Applications,J. ACM (1983), pp. 709–728. · Zbl 0627.68038
[11] Hong, J. W. and Rosenberg, A. L., Graphs that are Almost Binary Trees,SIAM J. Comput. 11, 2 (1982), pp. 227–242. · Zbl 0486.05055 · doi:10.1137/0211018
[12] Lipton, R. J. and Tarjan, R. E., Applications of a Planar Separator Theorem,SIAM J. Comput. 9, 3 (1980), pp. 615–627. · Zbl 0456.68077 · doi:10.1137/0209046
[13] Lopez, A. D. and Law, H.F.S., A Dense Gate Matrix Layout Method for MOS VLSI,IEEE Trans. Electron. Devices,27, 8 (1980), pp. 1671–1675. · doi:10.1109/T-ED.1980.20086
[14] Makedon, F., Layout Problems and Their Complexity, Ph.D. Thesis, EECS Department, Northwestern University (1982).
[15] Makedon, F., Papadimitriou, C. H., and Sudborough, I. H.. Topological Bandwidth,SIAM J. Algebraic Discrete Methods (1985). · Zbl 0573.05052
[16] Makedon, F., Simonson, S., and Sudborough, I. H., On the Complexity of Binary Tree Embeddings,Proc. 15th Southeastern Conf. on Combinatorics, Graph Theory and Computing (1984).
[17] Makedon, F. and Sudborough, I. H., Graph Layout Problems, inSurveys in Computer Science 1984, Herman Maurer, ed., B.I. Publishing, Zurich (1984).
[18] Megiddo, N., Hakimi, S. L., Garey, M., Johnson, D. S., and Papadimitriou, C. H., The Complexity of Searching a Graph,Proc. IEEE Foundations of Computer Science Symp. (1981), pp. 376–385. · Zbl 0637.68081
[19] Monien, B. and Sudborough, I. H., Min Cut isNP-complete for Edge Weighted Trees, unpublished manuscript (1985). · Zbl 0594.68042
[20] Papadimitriou, C. H., TheNP-completeness of the Bandwidth Minimization Problem,Computing 16 (1976), pp. 237–267. · Zbl 0321.65019 · doi:10.1007/BF02280884
[21] Parsons, T. D., The Search Number of a Connected Graph,Proc. 9th Southeastern Conf. on Combinatorics, Graph Theory and Computing (1978), pp. 549–554. · Zbl 0418.05022
[22] Paterson, M. S., Ruzzo, W. L., and Snyder, L., Bounds on Minimax Edge Length for Complete Binary Trees,ACM Theory of Computing Symp. (1981), pp. 293–299.
[23] Shiloach, Y., A Minimum Linear Arrangement Algorithm for Undirected Graphs,SIAM J. Comput. 8, 1 (1979), p. 15–32. · Zbl 0399.05021 · doi:10.1137/0208002
[24] Weinberger, A., Lange Scale Integration of MOS Complex Logic: A Layout Method,IEEE J. Solid-State Circuits 2 (1967), pp. 182–190. · doi:10.1109/JSSC.1967.1049816
[25] Wilber, R., White Pebbles Help,Proc. 17th Annual ACM Symp. on Theory of Computing (1985), pp. 103–112. · Zbl 0657.68049
[26] Yannakakis, M., A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees,J. ACM 32, 4 (1985), pp. 950–988. · Zbl 0633.68063 · doi:10.1145/4221.4228
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.