O. Aichholzer, A. García, J. Tejel, B. Vogtenhuber, and
A. Weinberger
Simple drawings are drawings of graphs in which the edges are Jordan arcs and
each pair of edges share at most one point (a proper crossing or a common
endpoint). A simple drawing is c-monotone if there is a point O such that
each ray emanating from O crosses each edge of the drawing at most once. We
introduce a special kind of c-monotone drawings that we call generalized
twisted drawings. A c-monotone drawing is generalized twisted if there is a
ray emanating from O that crosses all the edges of the drawing. Via this
class of drawings, we show that every simple drawing of the complete graph
with n vertices contains
pairwise disjoint edges
and a plane cycle (and hence path) of length
. Both results improve over best previously published lower bounds.
On the way we show several structural results and properties of generalized
twisted and c-monotone drawings, some of which we believe to be of
independent interest. For example, we show that a drawing D is c-monotone if
there exists a point O such that no edge of D is crossed more than once by
any ray that emanates from O and passes through a vertex of D.
