 Main
Lower Bounds and FixedParameter Tractability of Drawing Graphs
 Bannister, Michael James
 Advisor(s): Eppstein, David
Abstract
We investigate the problem of algorithmically drawing graphs, i.e., the process of creating geometric representations of graphs. We primarily consider nodelink diagrams, where the vertices of a graph are represented with dots and the edges of a graph are represented as piecewise smooth curves connecting those dots corresponding to their end points. Our contributions include hardness results going beyond $\NP$hardness and fixedparameter tractable algorithms for $\NP$hard problems.
Orthogonal drawing is a common graph drawing style in which the edges of a graph are drawn as polygonal chains of axisaligned segments. We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated better than within a polynomial factor of optimal in polynomial time unless $\P$ equals $\NP$. We also provide a fixedparameter tractable algorithm for testing whether a drawing can be compacted to a small number of rows.
Many wellknown graph drawing techniques have algebraic formulations. However, practical methods for producing such drawings use numerical approximations rather than constructing and then solving algebraic expressions representing their exact solutions. To explain this phenomenon, we use Galois theory to show that many variants of these problems have solutions that cannot be expressed by nested radicals or nested roots of lowdegree polynomials. Hence, such solutions cannot be computed exactly even in extended computational models that include such operations.
Finally, we investigate crossing minimization for $1$page and $2$page book drawings. In a $p$page book drawing, the vertices of the graph are placed on the $x$axis (or the spine), and the edges are drawn entirely in the upper halfplane. Each edge is assigned one of $p$ colors (or pages). In such drawing we only count crossings between edges in the same page. Since crossing minimization is an $\NP$hard problem we provide fixedparameter tractable algorithms; the parameters we consider are the $k$almost tree parameter, treewidth, and the crossing number.
Main Content
Enter the password to open this PDF file:













