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
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 21 May 2015 14:43
Last Modified: 21 May 2015 14:43
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1437

Actions (login required)

View Item View Item