Crossing numbers and combinatorial characterization of monotone drawings of KnK_n

preprint2014arXivOpen access

Abstract

In 1958, Hill conjectured that the minimum number of crossings in a drawing of KnK_n is exactly Z(n)=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋Z(n) = \frac{1}{4} \lfloor\frac{n}{2}\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor. Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by xx-monotone curves. In fact, our proof shows that the conjecture remains true for xx-monotone drawings of KnK_n in which adjacent edges may cross an even number of times, and instead of the crossing number we count the pairs of edges which cross an odd number of times. We further discuss a generalization of this result to shellable drawings, a notion introduced by Ábrego et al. We also give a combinatorial characterization of several classes of xx-monotone drawings of complete graphs using a small set of forbidden configurations. For a similar local characterization of shellable drawings, we generalize Carathéodory's theorem to simple drawings of complete graphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.