Universität zu Köln

Constrained Planarity and Augmentation Problems

Percan, Merijam (2007) Constrained Planarity and Augmentation Problems. PhD thesis, Universität zu Köln.

[img]
Preview
PDF
Download (1435Kb) | Preview

    Abstract

    A clustered graph C=(G,T) consists of an undirected graph G and a rooted tree T in which the leaves of T correspond to the vertices of G=(V,E). Each vertex m in T corresponds to a subset of the vertices of the graph called ``cluster''. c-planarity is a natural extension of graph planarity for clustered graphs, and plays an important role in automatic graph drawing. The complexity status of c-planarity testing is unknown. It has been shown by Dahlhaus, Eades, Feng, Cohen that c-planarity can be tested in linear time for c-connected graphs, i.e., graphs in which the cluster induced subgraphs are connected. In the first part of the thesis, we provide a polynomial time algorithms for c-planarity testing of specific planar clustered graphs: Graphs for which - all nodes corresponding to the non-c-connected clusters lie on the same path in T starting at the root of T, or graphs in which for each non-connected cluster its super-cluster and all its siblings in T are connected, - for all clusters m G-G(m) is connected. The algorithms are based on the concepts for the subgraph induced planar connectivity augmentation problem, also presented in this thesis. Furthermore, we give some characterizations of c-planar clustered graphs using minors and dual graphs and introduce a c-planar augmentation method. Parts II deals with edge deletion and bimodal crossing minimization. We prove that the maximum planar subgraph problem remains NP-complete even for non-planar graphs without a minor isomorphic to either K(5) or K(3,3), respectively. Further, we investigate the problem of finding a minimum weighted set of edges whose removal results in a graph without minors that are contractible onto a prespecified set of vertices. Finally, we investigate the problem of drawing a directed graph in two dimensions with a minimal number of crossings such that for every node the incoming and outgoing edges are separated consecutively in the cyclic adjacency lists. It turns out that the planarization method can be adapted such that the number of crossings can be expected to grow only slightly for practical instances.

    Item Type: Thesis (PhD thesis)
    Translated abstract:
    AbstractLanguage
    Ein Cluster-Graph C=(G,T) besteht aus einem ungerichteten Graphen G und einem gewurzelten Baum T in welchem die Blätter von T den Knoten von G=(V,E) entsprechen. Jeder Knoten m in T korrespondiert zu einer Knotenuntermenge genannt ``Cluster''. c-Planarität ist eine natürliche Erweiterung der Planarität für Cluster-Graphen und spielt eine bedeutende Rolle im Automatischen Zeichnen von Graphen. Die Komplexität des Testens auf c-Planarität ist bisher unbekannt. Es wurde von Dahlhaus, Eades, Feng, Cohen gezeigt, daß c-Planarität in linear Zeit für c-zusammenhängende Cluster-Graphen, also für solche in denen jeder induzierte Untergraph eines Custers zusammenhängend ist, getestet werden kann. Im ersten Teil dieser Dissertation stellen wir Algorithmen mit polynomieller Laufzeit vor, die c-Planarität für spezielle planare Cluster-Graphen testen: Graphen für die - alle Knoten mit korrespondierenden nicht zusammenhängenden Clustern auf demselben Pfad in T beginnend von der Wurzel liegen, oder Graphen in denen für jedes nicht zusammenhängende Cluster sein Vater und seine Geschwister in T zusammenhängend sind, - für alle Cluster m G-G(m) zusammenhängend ist. Die Algorithmen basieren auf den Konzepten des untergraph-induzerten planaren Augmentierungsproblems, welches auch in dieser Dissertation präsentiert wird. Zudem werden Charakterisierungen von c-planaren Cluster-Graphen mittels Minoren und dualen Graphen vorgestellt und eine c-planare Augmentierungsmethode erläutert. Teil II beschäftigt sich mit Kantenlöschungsproblemen und der bimodalen Kreuzungsminimierung. Es wird u.a. gezeigt, daß das Maximum Planare Untergraphenproblem schon für nicht planare Graphen ohne einen Minor isomorph entweder zu K(5) oder zu K(3,3) NP-vollständig ist. Das Studium möglicher polynomieller Spezialfälle unter (Tutte) Dekomposition ergab ein neues Problem zur Reduzierung des Zusammenhangs in bezug auf 3 Knoten, welches anschliessend analysiert wird. Das Problem einen gerichteten Graphen in zwei Dimensionen mit der minimalen Kreuzungsanzahl zu zeichnen, so daß für jeden Knoten die eingehenden von den ausgehenden Kanten getrennt werden, wird im letzten Kapitel der Dissertation behandelt. Es ergibt sich, daß die Planarisierungsmethode angepaßt werden kann, so daß die Kreuzungsanzahl für praktischen Instanzen nicht signifikant ansteigt.German
    Creators:
    CreatorsEmail
    Percan, Merijammeripercan@yahoo.de
    URN: urn:nbn:de:hbz:38-23419
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    Graphenzeichnen, Graphentheorie, c-Planarität, Cluster-Graphen, 2D-VisualisierungGerman
    Automatic Graph Drawing, Graph Theory, c-Planarity, Clustered Graphs, 2D-VisualizationEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: 2007
    Date Type: Completion
    Date of oral exam: 17 January 2008
    Full Text Status: Public
    Date Deposited: 16 Jun 2008 11:03:34
    Referee
    NameAcademic Title
    Jünger, MichaelProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/2341

    Actions (login required)

    View Item