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

Patrizio Angelini , Giordano Da Lozzo , Giuseppe Di Battista , Fabrizio Frati , Vincenzo Roselli

Authors on Pith no claims yet

classification 💻 cs.DS cs.CG

keywords planarityclustered-levelproblemst-levelbecomecasecomplexitydrawing

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

This paper has not been read by Pith yet.

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

discussion (0)