On the Complexity of Clustered-Level Planarity and T-Level Planarity

Clustered-Level Planarity is NP-complete. Reduction focused on the i-th triple $\langle \alpha,\beta,\delta\rangle$.

In this work we study two problems related to the drawing of level graphs, that is, T-Level Planarity and Clustered-Level Planarity. We show that both problems are NP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.

References:

• Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Vincenzo Roselli. The Importance of Being Proper (In Clustered-Level Planarity and T-Level Planarity). In, Christian Duncan, Antonios Symvonis, editors, Proc. 22nd International Symposium on Graph Drawing (GD ’14), Springer-Verlag, volume 8871 of Lecture Notes in Computer Science, pages 246-258, 2014.
• Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Vincenzo Roselli. On the Complexity of Clustered-Level Planarity and T-Level Planarity. Technical Report arXiv:1406.6533, Cornell University, 2014.