Charles Explorer logo
🇬🇧

Crossing numbers and combinatorial characterization of monotone drawings of K_n

Publication at Faculty of Mathematics and Physics |
2015

Abstract

Generalizing the result by Ábrego et al. for 2-page book drawings, we prove Hill's conjecture for plane drawings of the complete graph in which edges are represented by x-monotone curves. In fact, our proof shows that the conjecture remains true for x-monotone drawings 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 x-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.