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: http://dx.doi.org/10.1007/978-3-662-45803-7_21).

Full text not available from this repository.

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.

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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1437

Actions (login required)

View Item