Level Planarity

Beyond level planarity: Cyclic, torus, and simultaneous level planarity

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding …

Beyond Level Planarity

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding …

Planar Graphs with Vertices in Prescribed Regions: models, algorithms, and complexity

The volume and the complexity of structured relational information created and handled by modern information systems has drastically increased. More and more often, data are generated so quickly that they cannon even be completely displayed or …

The Importance of Being Proper - (In Clustered-Level Planarity and T-Level Planarity)

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 $\mathcal{NP}$-complete in the general case and that they become polynomial-time …

The Importance of Being Proper - (In Clustered-Level Planarity and T-Level Planarity)

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 $\mathcal{NP}$-complete in the general case and that they become polynomial-time …