Lower Bounds and Fixed-Parameter Tractability of Drawing Graphs

We investigate the problem of algorithmically drawing graphs, i.e., the process of creating geometric representations of graphs. We primarily consider node-link diagrams, where the vertices of a graph are represented with dots and the edges of a graph are represented as piece-wise smooth curves connecting those dots corresponding to their end points. Our contributions include hardness results going beyond $\NP$-hardness and fixed-parameter 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 axis-aligned 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 fixed-parameter tractable algorithm for testing whether a drawing can be compacted to a small number of rows.Many well-known 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 low-degree 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 half-plane. 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 fixed-parameter tractable algorithms; the parameters we consider are the $k$-almost tree parameter, treewidth, and the crossing number