The Importance of Being Proper

Angelini, Patrizio and Da Lozzo, Giordano and Di Battista, Giuseppe and Frati, Fabrizio and Roselli, Vincenzo (2014) The Importance of Being Proper. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 246-258(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_21
Classifications: G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.700 Layering
M Methods > M.999 Others
P Styles > P.180 Cluster
P Styles > P.480 Layered
P Styles > P.540 Planar
Z Theory > Z.750 Topology

Actions (login required)

View Item View Item