Graph Drawing is a field of research that has application in any field of science that needs to visualize binary relations. This thesis covers various problems arising when drawing graphs, both in theoretical and applied settings. In the first and more theory-based part, we start by discussing how and to which degree graph drawings can be used to visually prove graph properties (such as connectivity) in an effective manner. Both for these visual proofs and for graph drawings in general, the visual complexity determines how well humans are able to perceive and process them. We find it thus paramount to minimize the visual complexity of drawings. For example, one measure for the visual complexity of a straight-line node-link diagram is the number of segments used. We prove lower bounds on the segment number of some planar graph classes. These bounds tell us how (visually) complex node-link diagrams (a traditional drawing style) of these graphs must be at least. Next, we consider obstacle representations, which can be far less (visually) complex in some cases, however, (usually) at the expense of being harder to understand. Next, we investigate the coloring of mixed and directional interval graphs. While this in itself is not a drawing problem, it has, among others, application in the Sugiyama framework, which is a widely used framework for layered orthogonal graph drawing. In the final chapter of the first part, we consider drawings of level graphs on few levels under a given set of precedence constraints. The two problems considered in the second part are motivated by applications in biology. First, we propose a drawing style for visualizing multispecies coalescent trees, which are composed of a species tree and associated gene trees, and then investigate various drawing algorithms. Second, we propose a model for visualizing geophylogenies, that is, species trees that label sites on maps, and then analyze various variants and algorithms to draw them. / Graphenzeichnen ist eine wissenschaftliche Disziplin, die in jeder anderen Wissenschaft Anwendung findet, in der binäre Relationen visualisiert werden. Diese Dissertation behandelt diverse Probleme, die beim Zeichnen von Graphen auftreten, sowohl in praktischen als auch in theoretischen Kontexten. Im ersten und eher theorieorientierten Teil diskutieren wir, wie und inwieweit Zeichnungen von Graphen benutzt werden können, um Eigenschaften von Graphen (wie zum Beispiel Zusammenhang) auf effektive Weise visuell zu beweisen. Sowohl für diese visuellen Beweise als auch für Zeichnungen von Graphen im Allgemeinen bestimmt die visuelle Komplexität, wie gut Menschen dazu in der Lage sind, Graphen wahrzunehmen und zu verarbeiten. Daher halten wir es für äußerst wichtig, die visuelle Komplexität von Zeichnungen zu minimieren. Ein Maß für die visuelle Kom- plexität von geradelinigen Node-Link-Diagrammen (einem traditionellen Zeichenstil) ist die Anzahl der benutzten Liniensegmente. Wir beweisen untere Schranken für die Segmentzahl einiger planarer Graphklassen, welche wiederum implizieren, wie (visuell) komplex Node-Link-Diagramme dieser Graphen mindestens sind. Als nächs- tes betrachten wir Hindernisrepräsentationen, die in manchen Fällen eine deutlich geringere (visuelle) Komplexität haben können, dafür allerdings (oft) schwerer zu verstehen sind. Danach untersuchen wir das Färben von gemischten sowie gerichteten Intervallgra- phen. Während es sich dabei nicht direkt um ein Zeichenproblem handelt, findet es unter anderem Anwendung im Sugiyama-Framework, einem weit verbreiteten Frame- work zum Erstellen von orthogonalen Lagenzeichnungen. Im letzten Kapitel des ersten Teils betrachten wir das Zeichnen von Levelgraphen unter Vorrangbeschränkungen. Die beiden Probleme, die wir im zweiten Teil betrachten, sind durch Anwendungen in der Biologie motiviert. Als erstes schlagen wir einen Zeichenstil für das Visualisieren von Multispecies-Coalescent-Bäumen vor, welche aus einem Artenbaum und damit verknüpften Genbäumen bestehen, und geben diverse Zeichenalgorithmen für solche Bäume an. Als zweites schlagen wir ein Modell zum Visualieren von Artenbäumen vor, die Orte auf Landkarten beschriften, und analysieren diverse Varianten und Algorithmen um diese zu zeichnen.

The past few years have seen a tremendous increase in often irregularly structured data that can be represented most naturally and efficiently in the form of graphs. Making sense of incessantly growing graphs is not only a key requirement in applications like social media analysis or fraud detection but also a necessity in many traditional enterprise scenarios. Thus, a flexible approach for multidimensional analysis of graph data is needed. Whereas many existing technologies require up-front modelling of analytical scenarios and are difficult to adapt to changes, our approach allows for ad-hoc analytical queries of graph data. Extending our previous work on graph summarization, in this position paper we lay the foundation for large graph analytics to enable business intelligence on graph-structured data.

Center location on cactus graphs. The p-center problem has been shown to be NP-hard for case of a general graph, yet polynomial algorithms exist for the case of a tree graph. Specifically, we consider "cactus graphs" where each edge is contained in at most one cycle. We show that the p-center problem on this class can be solved in polynomial time using a decomposition algorithm. We partition the graph into a set of subgraphs which are then solved sequentially. The solutions to the subgraphs are linked by a single parameter. The algorithm runs in polynomial time. Locating capacity limited centers on trees. The uncapacitated p-center problem on trees is solvable in polynomial time. We extend this result to include the case where each center can serve a limited number of customers and show that the capacitated p-center on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. Center location on spheres. We discuss the unweighted center location problem. The following results are presented: (i) An O(n) time algorithm to solve the 1-center problem if the vertices are on one half of the sphere, and an O(n) time algorithm to check whether this condition holds. Both algorithms are based on presenting the problems as 3-dimensional convex programming problems with linear constraints and applying a pruning technique to find the optimum in O(n) time. (ii) An O(n$\sp3$ log n) time algorithm for the 2-center problem on the whole sphere. (iii) A reduction to show that the general p-center problem on a sphere is NP-hard. Locating hyperplanes on hypercubes. In linear regression models we are interested in locating a (d-1) dimensional hyperplane that will be as "close" as possible to existing vertices in the d-dimensional hypercube. The least squares criterion is usually applied for the linear fitting problem; while fitting according to the least absolute value ("minisum") seems to be "complicated". We solve fitting problems with the minisum criterion and present linear time algorithms when the dimension d is fixed. (Abstract shortened with permission of author.)

No description available.

No description available.

Thesis (Ph.D.)--University of Nebraska-Lincoln, 2006. / Title from title screen (site viewed on Feb. 5, 2007). PDF text: 66 p. : ill. (some col.) UMI publication number: AAT 3216432. Includes bibliographical references. Also available in microfilm and microfiche format.

No description available.

Hajós conjectured that, for any positive integer k, every graph containing no K_(k+1)-subdivision is k-colorable. This is true when k is at most three, and false when k exceeds six. Hajós' conjecture remains open for k=4,5. We will first present some known results on Hajós' conjecture. Then we derive a result on the structure of 2-connected graphs with no cycle through three specified vertices. This result will then be used for the proof of the main result of this thesis. We show that any possible counterexample to Hajós' conjecture for k=4 with minimum number of vertices must be 4-connected. This is a step in an attempt to reduce Hajós' conjecture for k=4 to the conjecture of Seymour that any 5-connected non-planar graph contains a K_5-subdivision.

Thesis (M.S.)--West Virginia University, 2002. / Title from document title page. Document formatted into pages; contains iii, 19 p. Includes abstract. Includes bibliographical references (p. 17-19).

Thesis (Ph. D.)--West Virginia University, 2003. / Title from document title page. Document formatted into pages; contains vi, 52 p. : ill. Includes abstract. Includes bibliographical references (p. 50-52).