Beyond level planarity

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 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 languageEnglish
Title of host publicationGraph Drawing and Network Visualization
Subtitle of host publication24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers
EditorsY. Hu, M. Nöllenburg
Place of PublicationDordrecht
PublisherSpringer
Pages482-495
ISBN (Electronic)978-3-319-50106-2
ISBN (Print)978-3-319-50105-5
DOIs
Publication statusPublished - 2016

Publication series

NameLecture Notes in Computer Science
Volume9801

Fingerprint

Dive into the research topics of 'Beyond level planarity'. Together they form a unique fingerprint.

Cite this