Deciding monotonicity of good drawings of the complete graph

O. Aichholzer, T. Hackl, A. Pilz, G. Salazar, and B. Vogtenhuber

Abstract:

We describe an $O(n^5)$ time algorithm for deciding whether a good drawing of the complete graph $K_n$, given in terms of its rotation system, can be re-drawn using only $x$-monotone arcs.

Reference: O. Aichholzer, T. Hackl, A. Pilz, G. Salazar, and B. Vogtenhuber. Deciding monotonicity of good drawings of the complete graph. In Proc. XVI Spanish Meeting on Computational Geometry (EGC 2015), pages 33-36, 2015.