On the pseudolinear crossing number. (English) Zbl 1359.05085
Summary: A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph \(G\) is the minimum number of pairwise crossings of edges in a pseudolinear drawing of \(G\). We establish several facts on the pseudolinear crossing number, including its computational complexity and its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by M. Schaefer [Electron. J. Comb. DS21, 90 p. (2013; Zbl 1267.05180)] in his comprehensive survey of the many variants of the crossing number of a graph.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
Keywords:
pseudoline arrangements; crossing number; pseudolinear crossing number; rectilinear crossing numberCitations:
Zbl 1267.05180References:
| [1] | D.Bienstock, Some provably hard crossing number problems, Discrete Comput Geom6(5) (1991), 443-459. · Zbl 0765.68202 |
| [2] | D.Bienstock and N.Dean, Bounds for rectilinear crossing numbers, J Graph Theory17(3) (1993), 333-348. · Zbl 0777.05049 |
| [3] | M.DeVos, B.Mohar, and RobertŠámal, Unexpected behaviour of crossing sequences, J Combin Theory Ser B101(6) (2011), 448-463. · Zbl 1234.05065 |
| [4] | Z.Dvořák and B.Mohar, Crossing‐critical graphs with large maximum degree, J Combin Theory Ser B100(4) (2010), 413-417. · Zbl 1247.05066 |
| [5] | I.Fáry, On straight line representation of planar graphs, Acta Univ Szeged Sect Sci Math11 (1948), 229-233. · Zbl 0030.17902 |
| [6] | M. R.Garey and D. S.Johnson, Crossing number is NP‐complete, SIAM J Algebraic Discrete Methods4(3) (1983) 312-316. · Zbl 0536.05016 |
| [7] | J. E.Goodman, Proof of a conjecture of Burr, Grünbaum, and Sloane, Discrete Math32(1) (1980), 27-35. · Zbl 0444.05029 |
| [8] | N. E.Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, In: Topology and Geometry—Rohlin Seminar, Lecture Notes in Computer Science 1346, Springer, Berlin, 1988, pp. 527-543. · Zbl 0667.52006 |
| [9] | J.Pach and G.Tóth, Monotone crossing number, Mosc J Comb Number Theory2(3) (2012), 18-33. · Zbl 1271.05067 |
| [10] | M. J.Pelsmajer, M.Schaefer, and D.Štefankovič, Odd crossing number and crossing number are not the same, Discrete Comput Geom39(1-3) (2008), 442-454. · Zbl 1143.05021 |
| [11] | G.Ringel, Teilungen der Ebene durch Geraden oder topologische Geraden, Math Z64 (1955), 79-102 (1956) (German). · Zbl 0070.16108 |
| [12] | M.Schaefer, Complexity of some geometric and topological problems, In: Graph drawing, Lecture Notes in Computer Science 5849, Springer, Berlin, 2010, pp. 334-344. · Zbl 1284.68305 |
| [13] | M.Schaefer, The graph crossing number and its variants: A survey, Electron J Combin, April 17, 2013, Dynamic Survey21, 90 pp. · Zbl 1267.05180 |
| [14] | P. W.Shor, Stretchability of pseudolines is NP‐hard, In: Applied Geometry and Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 4, American Mathematical Society, Providence, RI, 1991, pp. 531-554. · Zbl 0751.05023 |
| [15] | G.Tóth, Note on the pair‐crossing number and the odd‐crossing number, Discrete Comput Geom39(4) (2008), 791-799. · Zbl 1154.05318 |
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.
