Beyond Level Planarity

Angelini, Patrizio and Da Lozzo, Giordano and Di Battista, Giuseppe and Frati, Fabrizio and Partignani, Maurizio and Rutter, Ignaz (2016) Beyond Level Planarity. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 482-495(Official URL:

Full text not available from this repository.


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 of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity, are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels.

Item Type: Conference Paper
Classifications: M Methods > M.500 Layered
P Styles > P.480 Layered
P Styles > P.540 Planar

Actions (login required)

View Item View Item