Minimizing Switches in Cased Graph Drawings

Abstract

In einem cased drawing eines Graphens werden manche Kanten über anderen gezeichnet, um die negativen Auswirkungen von Kantenkreuzungen auf die Lesbarkeit zu minimieren. In diesem Kontext ist ein switch auf einer Kante definiert als zwei aufeinanderfolgende Kantenkreuzungen, wobei die Kante einer Kreuzung über und an der nächsten Kantenkreuzung hinter einer anderen Kante gezeichnet wird. In dieser Arbeit untersuchen wir verschiedene Probleme im Zusammenhang der Minimierung der Anzahl von switches—sowohl mit einer vorgegebenen Zeichnung eines Graphens als auch für nicht eingebettete Graphen.Unter anderem lösen wir eine offene Frage, die von Eppstein et al. 2007 vorgeschlagen wurde, in dem wir die NP-Schwere des Problems der Minimierung der maximalen Anzahl von switches pro Kante einer festgelegten Graphzeichnung nachweisen. Weiters zeigen wir, dass die Minimierung der Anzahl der Kanten mit mindestens einem switch NP-hart ist. Wir etablieren die Parametrisierbarkeit beider Probleme. Zuletzt definieren wir die Klasse aller Graphen, die mit höchstens k switches eingebettet werden können, kurz k-switch-planar graphs. Wir erläutern den Zusammenhang to biplanaran Graphen und zeigen, das jeder Graph mit höchstens einem switch pro Kante eingebettet werden kann.

In cased drawings of graphs, edges are drawn in front of others to reduce the negative impact of crossings on the readability of a graph. In this context, a switch on an edge is defined as two consecutive crossings, where the edge is drawn in front at one crossing and behind another edge at the next crossing. We investigate various problems of minimizing the number of switches—both in a fixed drawing as well as for non-embedded graphs.Among these results, we solve an open question proposed by Eppstein et al. in 2007 by establishing the NP-hardness of minimizing the maximum number of switches per edge in a fixed drawing. Further, we show that minimizing the number of edges with at least one switch is NP-hard. We establish fixed-parameter tractability for both problems. Lastly, we define the class of graphs embeddable with at most k switches, denoted as k-switch-planar graphs, inspired by the notion of k-gap-planar graphs introduced by Bae et al. in 2018. We show the relation of k-switch-planar graphs to biplanar graphs and prove that any graph can be embedded with at most 1 switch per edge.