Deciding monotonicity of simple drawings of the complete graph

Oswin Aichholzer, Thomas Hackl, Alexander Pilz +2

A drawing of a graph is {\em $x$-monotone} if every vertical line intersects each edge of the graph at most once. We present an $O(n^5)$ time algorithm for deciding whether a simpl…