UC Irvine

Drawing digraphs presents unique challenges that do not occur when drawing undirected graphs. Many digraphs tend to represent transitive relationships; that is they have a flow, and show a progression. When drawing digraphs the drawing style used must attempt to transmit this structural characteristic. In this dissertation, we study several optimization problems that are unique to drawing digraphs. First, we study the complexity the k-Modality problem of planar digraphs. Second, we turn to the practical task of drawing minimum width phylogenetic trees, which are used in the study of evolutionary relationships. Finally, we study a classical graph drawing problem, the One-Sided Crossing Minimization problem, in the novel evolving data setting.

An embedding is k-modal if every vertex is incident to at most k pairs of consecutive edges with opposite orientations. We study the k-Modality problem, which asks for the existence of a k-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks. We characterize the complexity of finding minimum modality embeddings, relate it to other graph drawing problems, both directed and undirected, and present fixed-parameter tractable algorithms for some important families.

We then study the problem of drawing small width phylogenetic trees. Phylogenetic trees are xiv

rooted trees that describe the evolutionary relationships derived from a common ancestor. In these the vertical distance represents the amount of time that passes; thus, the length of the edges is fixed. The Phylogenetic Tree Drawing problem asks for a minimum-width orthogonal upward drawing of a phylogenetic tree. We show that finding such a drawing is NP-hard for binary trees with unconstrained combinatorial order and provide a linear-time algorithm for ordered trees. We also study several heuristic algorithms for the unconstrained case and show their effectiveness through experimentation.

Finally, we study a restricted version of the One-Sided Crossing Minimization problem in the evolving data setting. Algorithms that solve this problem attempt to minimize the number of crossings between two adjacent layers when drawing layered graphs. We reduce the problem to that of sorting a list in the evolving data setting and study it from this viewpoint. In this model, a sorting algorithm maintains an approximation to the sorted order of a list of data items while simultaneously, with each comparison made by the algorithm, an adversary randomly swaps the order of adjacent items in the true sorted order. The experiments we perform in this dissertation provide empirical evidence that some quadratic-time algorithms such as insertion sort and bubble sort are asymptotically optimal for any constant rate of random swaps. In fact, these algorithms perform as well as or better than algorithms such as quicksort that are more efficient in the traditional algorithm analysis model.