Bounds for rectilinear crossing numbers. (English) Zbl 0777.05049
The crossing number and rectilinear crossing number of a graph \(G\) are denoted \(\text{cr}(G)\) and \(\text{cr}_ 1(G)\), respectively. For the 2- polygonal crossing number \(\text{cr}_ 2(G)\), each edge of \(G\) is represented by a polygonal line segment with at most two sections (rather than precisely one, as for \(\text{cr}_ 1(G))\). The following theorems are proved: (1) For every \(m>k\geq 4\), there exists a graph \(G\) with \(\text{cr}(G)=k\) and \(\text{cr}_ 1(G)\geq m\). (2) If \(\text{cr}(G)\leq 2\), then \(\text{cr}_ 1(G)=\text{cr}(G)\). (The authors announce that \(\text{cr}(G)\leq 3\) is sufficient, but prove only the weaker form in the present paper.) (3) For any graph \(G\), \(\text{cr}_ 2(G)\leq 2(\text{cr}(G))^ 2\).
Reviewer: A.T.White (Kalamazoo)
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Archdeacon, J. Graph Theory 12 pp 307– (1988) |
| [2] | Bienstock, J. Graph Theory 16 pp 389– (1992) |
| [3] | Bienstock, Discrete Comp. Geometry 6 pp 443– (1991) |
| [4] | Eggleton, Utilitas Math. 29 pp 149– (1986) |
| [5] | Erdös, Am. Math. Month. 80 pp 52– (1973) |
| [6] | Fáry, Acta Univ. Szeged Sect. Sci. Math. 11 pp 229– (1948) |
| [7] | , and , Small sets supporting Fáry embeddings of planar graphs. Proc. 20th Symposium on the Theory of Computing (1988) 426–433. |
| [8] | Garey, SIAM J. Alg. Discrete Math. 4 pp 312– (1983) |
| [9] | and , Computers and Intractability. W. H. Freeman, San Francisco (1979). |
| [10] | Guy, J. Combinat. Theory 4 pp 376– (1968) |
| [11] | Latest results on crossing numbers. Recent Trends in Graph Theory. Springer, New York (1971) 143–156. |
| [12] | Crossing numbers of graphs. Graph Theory and Applications. Springer, Berlin (1972) 111–124. |
| [13] | Jensen, J. Combinat. Theory 11 pp 212– (1971) |
| [14] | Kleitman, J. Combinat. Theory 9 pp 315– (1970) |
| [15] | Complexity Issues in VLSI. The MIT Press, Cambridge, MA (1983). |
| [16] | Richter, J. Graph Theory 12 pp 363– (1988) |
| [17] | Thomassen, J. Graph Theory 12 pp 335– (1988) |
| [18] | Tutte, Proc. London Math. Soc. 10 pp 304– (1960) |
| [19] | Tutte, J. Combinat. Theory 8 pp 45– (1970) |
| [20] | Wagner, Jber. Deutsch. Math. Verein 46 pp 26– (1936) |
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.
