| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 433953 | Theoretical Computer Science | 2015 | 9 Pages |
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 NPNP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Vincenzo Roselli,