The Importance of Being Proper - (In Clustered-Level Planarity and T-Level Planarity)
Clustered-Level Planarity is $\mathcal{NP}$-complete. Reduction focused on the i-th triple $\langle \alpha,\beta,\delta\rangle$
Abstract
In this paper 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 $\mathcal{NP}$-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.
Type
Publication
Theoretical Computer Science