Testing Cyclic Level and Simultaneous Level Planarity.
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter · arXiv (Cornell University) · 2015
In this paper we prove that testing the $\textit{cyclic level planarity}$ of a cyclic level graph is a polynomial-time solvable problem. This is achieved by introducing and studying a generalization of this problem, which we call $\textit{cyclic }{\cal T}\textit{-level planarity}$. Moreover, we show a complexity dichotomy for testing the $\textit{simultaneous level planarity}$ of a set of level graphs, with respect to both the number of level graphs and the number of levels.