On the Complexity of Clustered-Level Planarity and T-Level Planarity
Da Lozzo, Giordano
Di Battista, Giuseppe
Computer Science - Computational Geometry | Computer Science - Data Structures and Algorithms
acm: MathematicsofComputing_DISCRETEMATHEMATICS | TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
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 NP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.