Talks and Poster Presentations (with Proceedings-Entry):
T. Biedl, S. Chaplick, M Kaufmann, F. Montecchiani, M. Nöllenburg, C. Raftopoulou:
"Layered Fan-Planar Graph Drawings";
Talk: International Symposium on Mathematical Foundations of Computer Science (MFCS),
Prag, Tschechien;
2020-08-24
- 2020-08-28; in: "45th International Symposium on Mathematical Foundations of Computer Science",
LIPICS,
170
(2020),
ISBN: 978-3-95977-159-7;
1
- 13.
English abstract:
In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. In this
paper, we study fan-planar drawings that use h (horizontal) layers and are proper, i.e., edges connect
adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence
of such drawings is fixed-parameter tractable in h, via a reduction to a similar result for planar
graphs by Dujmovic et al. If the embedding is not fixed, then we give partial results for h = 2: It
was already known how to test the existence of fan-planar proper 2-layer drawings for 2-connected
graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting
results for graphs with a fan-planar proper h-layer drawing; in particular we bound their pathwidth
and show that they have a bar-1-visibility representation.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.14
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_292478.pdf
Created from the Publication Database of the Vienna University of Technology.