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 Np-complete in the general case and that they become polynomial-time solvable when restricted to proper instances. (C) 2015 Elsevier B.V. All rights reserved.