The Importance of Being Proper (In Clustered-Level Planarity and T-Level Planarity)
Martedì 16 settembre 2014 Ore 12:00-13:00
Sala Riunioni, 1° piano, Dipartimento di Ingegneria
Via della Vasca Navale, 79, Roma
Giordano Da Lozzo
The Importance of Being Proper
(In Clustered-Level Planarity and T-Level Planarity)
Abstract. A level graph is proper if each of its edges spans just two consecutive levels. Several papers dealing with the construction of level drawings of level graphs assume that the input graph is proper. Otherwise, they suggest to make it proper by “simply adding dummy vertices” along the edges spanning more than two levels. In this work we show that this apparently innocent augmentation has dramatic consequences if, instead of constructing just a level drawing, we are also interested in representing additional constraints. We study two problems, called T-LEVEL PLANARITY and CLUSTERED-LEVEL PLANARITY, related to the drawing of level graphs equipped either with a clustering of their vertices or with consecutivity constraints on the orderings of the vertices along the levels, respectively. We show that both problems are NP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances.
Joint work with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vincenzo Roselli
