On Layered Drawings of Planar Graphs
Sarah Lutteropp · 2014
A graph is k-level planar if it admits a planar drawing in which each vertex is mapped to one of k horizontal parallel lines and the edges are drawn as non-crossing y-monotone line segments between these lines. It is not known whether the decision problem of a graph being k-level planar is solvable in polynomial time complexity (in P) or not. However, if the layer assignment, i.e. the mapping of each vertex to a line, is given, we can construct a level planar embedding in linear time if it exists. In case there is no level planar embedding, one can try to minimize the total number of crossings, which is known to be NP-complete. It is easy to construct an example of a planar graph with a layer assignment that results in a non level planar graph. Motivated by this fact we investigate the situation where it is allowed to perform as few modifications to the layer assignments as possible in order to obtain a level planar drawing. We give an extensive overview of the current state of research related to level planarity and provide a heuristic for changing the layer assignment as little as possible by swapping the layer assignments of pairs of vertices or moving vertices to other layers (with or without introducing new layers) in order to get a level planar result. Deutsche Zusammenfassung Ein Graph heist k-level planar, falls man ihn so in der Ebene zeichnen kann, dass die Knoten auf k horizontalen parallelen Geraden angeordnet sind. Die Kanten durfen sich nicht kreuzen und verlaufen als y-monotone Kurven zwischen diesen Geraden. Die Menge aller Knoten auf der gleichen Geraden heist Schicht. Es ist unklar, ob die Frage, ob ein gegebener Graph k-level planar ist in P liegt oder nicht. Falls die Zuordnungen von Knoten auf Geraden im Voraus bekannt sind, kann mit linearem Zeitaufwand eine solche Einbettung gefunden werden, falls sie existiert. Wenn keine solche Einbettung existiert, kann man versuchen, die Anzahl Kreuzungen zu minimieren. Dies ist bekannterweise NP-vollstandig. In dieser Arbeit versuchen wir, moglichst wenige der vorgegebenen Schichtzuordnungen zu verandern, sodass wir eine level planare Zeichnung des Graphen erhalten. Wir geben einen ausfuhrlichen Uberblick zum aktuellen Stand der Forschung zu level planarity und entwickeln eine Heuristik, die versucht durch moglichst wenige Vertauschungen oder Verschiebungen von Knoten zwischen Schichten eine level planare Zeichnung des gegebenen Graphen zu ermoglichen.