On 3-decomposable geometric drawings of K_n

arXiv0712.4255MaRDI QIDQ6207944FDOQ6207944

B. M. Ábrego, J. Leaños, Gelasio Salazar, Silvia Fernández-Merchant

Publication date: 27 December 2007

Abstract: The point sets of all known optimal rectilinear drawings of

K_{n}

share an unmistakeable clustering property, the so--called {em 3--decomposability}. It is widely believed that the underlying point sets of all optimal rectilinear drawings of

K_{n}

are 3--decomposable. We give a lower bound for the minimum number of

(l e k)

--sets in a 3--decomposable

n

--point set. As an immediate corollary, we obtain a lower bound for the crossing number

c r (d d)

of any rectilinear drawing

d d

of

K_{n}

with underlying 3--decomposable point set, namely

. This closes this gap between the best known lower and upper bounds for the rectilinear crossing number

c r (K_{n})

of

K_{n}

by over 40%, under the assumption of 3--decomposability.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

This page was built for publication: On 3-decomposable geometric drawings of $K_n$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6207944)