Beyond level planarity

P. Angelini; G. Da Lozzo; G. Di Battista; F. Frati; M. Patrignani; I. Rutter

doi:10.1007/978-3-319-50106-2_37

Beyond level planarity

P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, I. Rutter

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

14 Citations (Scopus)

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.
Research was partially supported by DFG grant Ka812/17-1, by MIUR project AMANDA, prot. 2012C4E3KT_001, and by DFG grant WA 654/21-1.

Original language	English
Title of host publication	Graph Drawing and Network Visualization
Subtitle of host publication	24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers
Editors	Y. Hu, M. Nöllenburg
Place of Publication	Dordrecht
Publisher	Springer
Pages	482-495
ISBN (Electronic)	978-3-319-50106-2
ISBN (Print)	978-3-319-50105-5
DOIs	https://doi.org/10.1007/978-3-319-50106-2_37
Publication status	Published - 2016

Publication series

Name	Lecture Notes in Computer Science
Volume	9801

Access to Document

10.1007/978-3-319-50106-2_37

Cite this

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., & Rutter, I. (2016). Beyond level planarity. In Y. Hu, & M. Nöllenburg (Eds.), Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers (pp. 482-495). (Lecture Notes in Computer Science; Vol. 9801). Springer. https://doi.org/10.1007/978-3-319-50106-2_37

@inproceedings{7d5e733277954f31a124225a7cca5b11,

title = "Beyond level planarity",

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.Research was partially supported by DFG grant Ka812/17-1, by MIUR project AMANDA, prot. 2012C4E3KT_001, and by DFG grant WA 654/21-1.",

author = "P. Angelini and {Da Lozzo}, G. and {Di Battista}, G. and F. Frati and M. Patrignani and I. Rutter",

year = "2016",

doi = "10.1007/978-3-319-50106-2_37",

language = "English",

isbn = "978-3-319-50105-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "482--495",

editor = "Y. Hu and M. N{\"o}llenburg",

booktitle = "Graph Drawing and Network Visualization",

address = "Germany",

}

Angelini, P, Da Lozzo, G, Di Battista, G, Frati, F, Patrignani, M & Rutter, I 2016, Beyond level planarity. in Y Hu & M Nöllenburg (eds), Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9801, Springer, Dordrecht, pp. 482-495. https://doi.org/10.1007/978-3-319-50106-2_37

Beyond level planarity. / Angelini, P.; Da Lozzo, G.; Di Battista, G. et al.
Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. ed. / Y. Hu; M. Nöllenburg. Dordrecht: Springer, 2016. p. 482-495 (Lecture Notes in Computer Science; Vol. 9801).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Beyond level planarity

AU - Angelini, P.

AU - Da Lozzo, G.

AU - Di Battista, G.

AU - Frati, F.

AU - Patrignani, M.

AU - Rutter, I.

PY - 2016

Y1 - 2016

N2 - 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.Research was partially supported by DFG grant Ka812/17-1, by MIUR project AMANDA, prot. 2012C4E3KT_001, and by DFG grant WA 654/21-1.

AB - 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.Research was partially supported by DFG grant Ka812/17-1, by MIUR project AMANDA, prot. 2012C4E3KT_001, and by DFG grant WA 654/21-1.

U2 - 10.1007/978-3-319-50106-2_37

DO - 10.1007/978-3-319-50106-2_37

M3 - Conference contribution

SN - 978-3-319-50105-5

T3 - Lecture Notes in Computer Science

SP - 482

EP - 495

BT - Graph Drawing and Network Visualization

A2 - Hu, Y.

A2 - Nöllenburg, M.

PB - Springer

CY - Dordrecht

ER -

Angelini P, Da Lozzo G, Di Battista G, Frati F, Patrignani M, Rutter I. Beyond level planarity. In Hu Y, Nöllenburg M, editors, Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. Dordrecht: Springer. 2016. p. 482-495. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-50106-2_37

Beyond level planarity

Abstract

Publication series

Access to Document

Fingerprint

Cite this