Improved bounds for the crossing numbers of Km, n and Kn

E De Klerk, J Maharry, DV Pasechnik, RB Richter… - SIAM Journal on Discrete …, 2006 - SIAM
It has been long conjectured that the crossing number \Cr(K_m,n) of the complete bipartite
graph K_m,n equals the Zarankiewicz number Z(m,n):=m-12m2n-12n2. Another …

Abstract order type extension and new results on the rectilinear crossing number

O Aichholzer, H Krasser - Proceedings of the twenty-first annual …, 2005 - dl.acm.org
We extend the order type data base of all realizable order types in the plane to point sets of
cardinality 11. More precisely, we provide a complete data base of all combinatorial different …

Crossing Numbers and Combinatorial Characterization of Monotone Drawings of

M Balko, R Fulek, J Kynčl - Discrete & Computational Geometry, 2015 - Springer
In 1958, Hill conjectured that the minimum number of crossings in a drawing of K_n K n is
exactly Z (n)= 1 4\big ⌊ n 2\big ⌋\big ⌊ n-1 2\big ⌋\big ⌊ n-2 2\big ⌋\big ⌊ n-3 2\big ⌋ Z (n) …

The Rectilinear Crossing Number of K n : Closing in (or Are We?)

BM Ábrego, S Fernández-Merchant… - Thirty essays on geometric …, 2013 - Springer
The calculation of the rectilinear crossing number of complete graphs is an important open
problem in combinatorial geometry, with important and fruitful connections to other classical …

On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of Kn

BM Ábrego, M Cetina, S Fernández-Merchant… - Discrete & …, 2012 - Springer
Let P be a set of points in general position in the plane. Join all pairs of points in P with
straight line segments. The number of segment-crossings in such a drawing, denoted by …

New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of Kn

O Aichholzer, J Garcia, D Orden, P Ramos - Discrete & Computational …, 2007 - Springer
We provide a new lower bound on the number of (≤ k)-edges of a set of n points in the
plane in general position. We show that for 0≦k≦⌊(n-2)/2⌋ the number of (≤ k)-edges is at …

[PDF][PDF] Crossing numbers of graphs: A bibliography

I Vrt'o - Available electronically at ftp://ifi. savba. sk/pub/imrich …, 2008 - Citeseer
62] Turan, P., A note of welcome, J. Graph Theory 1 (1977) 7-9. 63] Dambitis, J., An
algorithm for superimposing a nonplanar graph onto the plane with nearly minimal number …

[HTML][HTML] 3-symmetric and 3-decomposable geometric drawings of Kn

BM Ábrego, M Cetina, S Fernández-Merchant… - Discrete Applied …, 2010 - Elsevier
Even the most superficial glance at the vast majority of crossing-minimal geometric drawings
of Kn reveals two hard-to-miss features. First, all such drawings appear to be 3-fold …

Geometric drawings of Kn with few crossings

BM Ábrego, S Fernández-Merchant - Journal of Combinatorial Theory …, 2007 - Elsevier
We give a new upper bound for the rectilinear crossing number cr¯(n) of the complete
geometric graph Kn. We prove that cr¯(n)⩽ 0.380559 (n4)+ Θ (n3) by means of a new …

On the crossing number of complete graphs

O Aichholzer, F Aurenhammer, H Krasser - Computing, 2006 - Springer
Let (G) denote the rectilinear crossing number of a graph G. We determine (K 11)= 102 and
(K 12)= 153. Despite the remarkable hunt for crossing numbers of the complete graph K n …