Minimizing Switches in Cased Graph Drawings

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.