Engineering an algorithm for strict outerconfluent graph drawings

Abstract

Eine konfluente Zeichnung eines Graphens ist eine Zeichnung, in welcher die Knoten des Graphens als Punkte in der Ebene und die Kanten als glatte Pfade durch ein planares System von Kreuzungen und Bögen dargestellt werden. Als außen-konfluente Zeichnung werden jene konfluente Zeichnungen bezeichnet bei welchen alle Knoten auf der Außenfläche liegen. Schlussendlich ist eine strikte außen-konfluente Zeichnung eine außen-konfluente Zeichnung bei der es keine zwei unterschiedliche Pfade zwischen zwei Knoten gibt und kein Knoten einen Pfad zu sich selbst aufweist. Eppstein et al.(2016) beschrieben auf einem sehr abstrakten Level einen Algorithmus, welcher für einen gegebenen Graphen zusammen mit einer Ordnung der Knoten feststellt ob dieser Graph mit dieser Ordnung eine strikt außen-konfluente Zeichnung besitzt oder nicht. Bisher wurde dieser Algorithmus jedoch noch nicht implementiert. Ein Teil meiner Arbeit ist die Implementierung dieses Algorithmus sowie eine detailierte Beschreibung des Algorithmus. Mit der korrekten Implementierung des Algorithmus war es uns dann möglich zu testen ob unterschiedliche Graphklassen solche Zeichnungen besitzen oder nicht. Ein Ergebnis dieser Auswertung ist, dass bipartite Permutationsgraphen nicht immer eine solche Zeichnung besitzen, obwohl dies unsere Annahme war.

A confluent drawing is a drawing of a graph where vertices are presented as points in the plane and edges as smooth paths through a planar system of junctions and arcs. An outerconfluent drawing is a confluent drawing in which all vertices of the graph lie on the boundary of the outer face of the drawing. Furthermore, a strict outerconfluent drawing is an outerconfluent drawing with the additional constraint that there is no self-loop between two vertices and that there exists at most one path between two vertices. Eppstein et al.(2016) abstractly defined an algorithm for checking a given graph together with a vertex order for a strict outerconfluent drawing. However, this algorithm has never been implemented. As part of this thesis the algorithm was implemented and a detailed description of each individual step is presented. With the correct implementation we tried to find different classes of graphs which do or do not obtain strict outerconfluent drawings. One of our results is that bipartite permutation graphs do not obtain strict outerconfluent drawings although this was suspected in a recent paper by Förster et al.(2019).