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.

Angelini, P., DA LOZZO, G., DI BATTISTA, G., Frati, F., Patrignani, M., Rutter, I. (2016). Beyond level planarity. In Graph Drawing and Network Visualization 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers (pp.482-495). Springer Verlag [10.1007/978-3-319-50106-2_37].

Beyond level planarity

ANGELINI, PATRIZIO;DA LOZZO, GIORDANO;DI BATTISTA, Giuseppe;FRATI, FABRIZIO;PATRIGNANI, Maurizio;
2016-01-01

Abstract

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.
2016
9783319501055
Angelini, P., DA LOZZO, G., DI BATTISTA, G., Frati, F., Patrignani, M., Rutter, I. (2016). Beyond level planarity. In Graph Drawing and Network Visualization 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers (pp.482-495). Springer Verlag [10.1007/978-3-319-50106-2_37].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/316406
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 10
social impact