×

Some provably hard crossing number problems. (English) Zbl 0765.68202

Summary: This paper presents a connection between the problem of drawing a graph with the minimum number of edge crossings, and the theory of arrangements of pseudolines, a topic well-studied by combinatorialists. In particular, we show that any given arrangement can be forced to occur in every minimum crossing drawing of an appropriate graph. Using some recent results of Goodman, Pollack, and Sturmfels, this yields that there exists no polynomial-time algorithm for producing a straight-line drawing of a graph, which achieves the minimum number of crossings from among all such drawings. While this result has no bearing on the P versus NP question, it is fairly negative with regard to applications. We also study the problem of drawing a graph with polygonal edges, to achieve the (unrestricted) minimum number of crossings. Here we obtain a tight bound on the smallest number of breakpoints which are required in the polygonal lines.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
52A37 Other problems of combinatorial convexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] D. Bienstock and N. Dean, Bounds on rectilinear crossing numbers, submitted. · Zbl 0777.05049
[2] D. Bienstock and N. Dean, New results on polygonal crossing numbers, submitted. · Zbl 0760.05028
[3] H. deFraysseix, R. Pollack, and J. Pach, Small sets supporting Fáry embeddings of planar graphs,Proc. 20th STOC (1988), pp. 426-433.
[4] P. Erdös and R. K. Guy, Crossing number problems,Amer. Math. Monthly80 (1973), 52-58. · Zbl 0264.05109 · doi:10.2307/2319261
[5] M. R. Garey and D. S. Johnson, Crossing number is NP-complete,SIAM J Algebraic Discete Methods4 (1983), 312-316. · Zbl 0536.05016 · doi:10.1137/0604033
[6] J. E. Goodman, Proof of a conjecture of Burr, Grünbaum, and Sloane,Discrete Math.32 (1980), 27-35. · Zbl 0444.05029 · doi:10.1016/0012-365X(80)90096-5
[7] J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane,J. Combin. Theory Ser. A29 (1980), 230-235. · Zbl 0448.05016
[8] J. E. Goodman and R. Pollack, Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines,J. Combin. Theory Ser. A29 (1980) 385-390. · Zbl 0457.51006 · doi:10.1016/0097-3165(80)90038-2
[9] J. E. Goodman and R. Pollack, Multidimensional sorting.SIAM J. Comput.12 (1983), 484-501. · Zbl 0525.68038 · doi:10.1137/0212032
[10] J. E. Goodman and R. Pollack, Semispaces of configurations, cell complexes of arrangements,J. Combin. Theory Ser. A37 (1984), 257-293. · Zbl 0551.05002 · doi:10.1016/0097-3165(84)90050-5
[11] J. E. Goodman and R. Pollack, Polynomial realization of pseudoline arrangements,Comm. Pure Appl. Math.XXXVIII (1985), 725-732. · Zbl 0609.51021 · doi:10.1002/cpa.3160380606
[12] J. E. Goodman and R. Pollack, There are asymptotically fewer polytopes than we thought,Bull. Amer. Math. Soc.14 (1986), 127-129. · Zbl 0585.52003 · doi:10.1090/S0273-0979-1986-15415-7
[13] J. E. Goodman and R. Pollack, Upper bounds for configurations and polytopes in ℝd,Discrete Comput. Geom.1 (1986), 229-237. · Zbl 0609.52004 · doi:10.1007/BF02187696
[14] J. E. Goodman, R. Pollack, and B. Sturmfels, Coordinate representation of order types requires exponential storage,Proc. 22st STOC (1989), pp. 405-410.
[15] B. Grünbaum,Arrangements and Spreads, CBMS Regional Conference Series in Applied Mathematics, Vol. 10, American Mathematical Society, Providence, RI (1972). · Zbl 0249.50011
[16] J. Kratochvil and J. Matousek, Intersection graphs of segments, submitted. · Zbl 0808.68075
[17] F. T. Leighton,Complexity Issues in VLSI, MIT Press, Cambridge, MA (1983).
[18] Mnëv, N. E.; Viro, O. Ya. (ed.), The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, No. Vol. 1346, 527-544 (1988), Berlin · Zbl 0667.52006 · doi:10.1007/BFb0082792
[19] G. Ringel, Teilungen der Ebene durch Geraden oder topologische Geraden,Math. Z.64 (1956), 79-102. · Zbl 0070.16108 · doi:10.1007/BF01166556
[20] W. Schnyder, Embedding planar graphs on the grid, Preliminary report, Louisiana State University, Baton Rouge. · Zbl 0786.05029
[21] P. Shor, Stretchability of pseudolines is NP-Hard, Manuscript (1990). · Zbl 0751.05023
[22] C. Thomassen, Rectilinear drawings of graphs,J. Graph Theory12 (1988), 335-341. · Zbl 0649.05051 · doi:10.1002/jgt.3190120306
[23] W. T. Tutte, Toward a theory of crossing numbers,J. Combin. Theory8 (1970), 45-53. · Zbl 0187.20803 · doi:10.1016/S0021-9800(70)80007-2
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.