The importance of being proper: (In clustered-level planarity and T-level planarity)

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 NPNP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.