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.

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.

http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.14

https://publik.tuwien.ac.at/files/publik_292478.pdf

Created from the Publication Database of the Vienna University of Technology.