Universität zu Köln

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

Preview

PDF MerijamPercanDiss.pdf Download (1MB)

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 title:	Title Language Bedingte Planaritäts- und Augmentierungsprobleme German
Translated abstract:	Abstract Language 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:	Creators Email ORCID ORCID Put Code Percan, Merijam meripercan@yahoo.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-23419
Date:	2007
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Graphenzeichnen, Graphentheorie, c-Planarität, Cluster-Graphen, 2D-Visualisierung German Automatic Graph Drawing, Graph Theory, c-Planarity, Clustered Graphs, 2D-Visualization English
Date of oral exam:	17 January 2008
Referee:	Name Academic Title Jünger, Michael Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/2341