Universität zu Köln

Algorithms for Incremental Planar Graph Drawing and Two-page Book Embeddings

Gronemann, Martin (2015) Algorithms for Incremental Planar Graph Drawing and Two-page Book Embeddings. PhD thesis, Universität zu Köln.

[img]
Preview
PDF - Published Version
Download (1437Kb) | Preview

    Abstract

    Subject of this work are two problems related to ordering the vertices of planar graphs. The first one is concerned with the properties of vertex-orderings that serve as a basis for incremental drawing algorithms. Such a drawing algorithm usually extends a drawing by adding the vertices step-by-step as provided by the ordering. In the field of graph drawing several orderings are in use for this purpose. Some of them, however, lack certain properties that are desirable or required for classic incremental drawing methods. We narrow down these properties, and introduce the bitonic st-ordering, an ordering which combines the features only available when using canonical orderings with the flexibility of st-orderings. The additional property of being bitonic enables an st-ordering to be used in algorithms that usually require a canonical ordering. With this in mind, we describe a linear-time algorithm that computes such an ordering for every biconnected planar graph. Unlike canonical orderings, st-orderings extend to directed graphs, in particular planar st-graphs. Being able to compute bitonic st-orderings for planar st-graphs is of particular interest for upward planar drawing algorithms, since traditional incremental algorithms for undirected planar graphs might be adapted to directed graphs. Based on this observation, we give a full characterization of the class of planar st-graphs that admit such an ordering. This includes a linear-time algorithm for recognition and ordering. Furthermore, we show that by splitting specific edges of an instance that is not part of this class, one is able to transform it into one for which then such an ordering exists. To do so, we describe a linear-time algorithm for finding the smallest set of edges to split. We show that for a planar st-graph G=(V,E), |V|−3 edge splits are sufficient and every edge is split at most once. This immediately translates to the number of bends required for upward planar poly-line drawings. More specifically, we show that every planar st-graph admits an upward planar poly-line drawing in quadratic area with at most |V|−3 bends in total and at most one bend per edge. Moreover, the drawing can be obtained in linear time. The second part is concerned with embedding planar graphs with maximum degree three and four into books. Besides providing a simplified incremental linear-time algorithm for embedding triconnected 3-planar graphs into a book of two pages, we describe a linear-time algorithm to compute a subhamiltonian cycle in a triconnected 4-planar graph.

    Item Type: Thesis (PhD thesis)
    Translated abstract:
    AbstractLanguage
    Diese Arbeit beschäftigt sich mit zwei Problemen bei denen es um Knotenordnungen in planaren Graphen geht. Hierbei werden als erstes Ordnungen betrachtet, die als Grundlage für inkrementelle Zeichenalgorithmen dienen. Solche Algorithmen erweitern in der Regel eine vorhandene Zeichnung durch schrittweises Hinzufügen von Knoten in der durch die Ordnung gegebene Reihenfolge. Zu diesem Zweck kommen im Gebiet des Graphenzeichnens verschiedene Ordnungstypen zum Einsatz. Einigen dieser Ordnungen fehlen allerdings gewünschte oder sogar für einige Algorithmen notwendige Eigenschaften. Diese Eigenschaften werden genauer untersucht und dabei ein neuer Typ von Ordnung entwickelt, die sogenannte bitonische st-Ordnung, eine Ordnung, welche Eigenschaften kanonischer Ordnungen mit der Flexibilität herkömmlicher st-Ordnungen kombiniert. Die zusätzliche Eigenschaft bitonisch zu sein ermöglicht es, eine st-Ordnung wie eine kanonische Ordnung zu verwenden. Es wird gezeigt, dass für jeden zwei-zusammenhängenden planaren Graphen eine bitonische st-Ordnung in linearer Zeit berechnet werden kann. Im Gegensatz zu kanonischen Ordnungen, können st-Ordnungen naturgemäß auch für gerichtete Graphen verwendet werden. Diese Fähigkeit ist für das Zeichnen von aufwärtsplanaren Graphen von besonderem Interesse, da eine bitonische st-Ordnung unter Umständen es erlauben würde, vorhandene ungerichtete Zeichenverfahren für den gerichteten Fall anzupassen. Basierend auf dieser Beobachtung wird eine Teilmenge der planaren st-Graphen charakterisiert, für die eine solche Ordnung existiert. Zusätzlich wird ein Linearzeit-Algorithmus vorgestellt, der diese Graphen erkennt und eine bitonische st-Ordnung berechnet. Für die übrigen planaren st-Graphen wird gezeigt, dass mittels Unterteilung spezifischer Kanten eine Instanz augmentiert werden kann, so dass für diese eine bitonische st-Ordnung existiert. Dabei bestimmt ein Linearzeit-Algorithmus die kleinste Kantenmenge für den Unterteilungsschritt. Weiterhin wird gezeigt, dass für einen planaren st-Graphen G=(V,E) diese Menge nicht mehr als |V|−3 Kanten umfasst und jede Kante höchstens einmal unterteilt werden muss. Dieses Resultat lässt sich sofort übertragen auf die Anzahl der benötigten Knicke in aufwärtsplanaren Zeichnungen. Es wird ein Algorithmus angegeben, der eine aufwärtsplanare Zeichnung mit quadratischer Fläche, höchstens |V|−3 Knicken insgesamt und maximal einem Knick pro Kante in linearer Zeit erstellt. Der zweite Teil der Arbeit widmet sich der Einbettung von planaren Graphen mit Maximalgrad drei und vier in Büchern mit zwei Seiten. Neben einem vereinfachten inkrementellen Linearzeit-Algorithmus für drei-zusammen-hängende 3-planare Graphen, wird auch ein Linearzeit-Algorithmus für den 4-planaren Fall vorgestellt.German
    Creators:
    CreatorsEmail
    Gronemann, Martingronemann@informatik.uni-koeln.de
    URN: urn:nbn:de:hbz:38-63290
    Subjects: Data processing Computer science
    Mathematics
    Uncontrolled Keywords:
    KeywordsLanguage
    graph drawingEnglish
    vertex orderingEnglish
    book embeddingEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: 2015
    Date Type: Publication
    Date of oral exam: 23 June 2015
    Full Text Status: Public
    Date Deposited: 22 Sep 2015 15:20:32
    Referee
    NameAcademic Title
    Jünger, MichaelProf. Dr.
    Chimani, MarkusProf. Dr.
    Speckmann, BettinaProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/6329

    Actions (login required)

    View Item