Graph Drawing Beyond the Beaten Tracks

Abstract

Graph drawing is a well-established research area in theoretical computer science with an active research community that studies the embedding of graphs on surfaces such as the Euclidean plane. While traditional results stem from discrete maths, graph embeddings have become more widespread with the emergence of computing technology. Two important applications are the design of computer chips and various diagram types such as UML and BPMN whose development was possible due to the ubiquity of computers in professional environments. While the traditional settings emerging from these newer applications are by now well studied, research has started to focus on advanced settings whose analysis becomes more technically involved. One of the most important research directions of this type is known as graph drawing beyond planarity and studies drawings of graphs where the types of edge intersections are restricted. In this thesis, we consider three such settings that go beyond the beaten tracks.

The most important drawing model in diagramming applications are orthogonal drawings in which edges are represented by polylines whose segments are axis-aligned. Unsurprisingly, there exists a large body of research focusing mostly on planar orthogonal drawings. We investigate two settings that have been proposed in the literature that extend beyond this traditional model: In the smooth orthogonal drawing model, bends are replaced by circular arcs, while in octilinear drawings, segments of polylines may additionally have slopes ±1. In the first part of this thesis, we show several new results for these “beyond orthogonal” drawing styles: First, we characterize the relationship between the classes of graphs that admit smooth orthogonal and octilinear drawings, respectively. Second, we prove that techniques which diverge from the traditional ones used for orthogonal graph drawings are needed to compute smooth orthogonal and octilinear drawings of minimal curve complexity. Third, we give a drawing algorithm that guarantees several desirable properties. Finally, we also extend the study of orthogonal and smooth orthogonal drawings to the 1-planar setting where edges may be intersected at most once. Here, we provide algorithms which compute drawings whose curve complexity we prove to be worst-case optimal in almost all scenarios.

A graph drawing type that emerged from applications in VLSI chip design are linear layouts. In a linear layout, vertices are totally ordered on a line called spine while edges are drawn entirely above the spine. In a stack layout, the edges are additionally colored so that no two edges of the same color class intersect. This model has been deeply studied especially for planar graphs. The most important result in this field is that four colors suffice for the edges of any planar graph. A related model called queue layouts, however, has proven to be much more difficult to analyze. In a queue layout, edges are also colored, in contrast to stack layouts however, edges of the same color class may intersect but not nest. For more than 25 years the conjecture that a constant number of colors suffices for planar graphs had been open. In the second part of the thesis, we show that for planar graphs of bounded degree this is indeed true. We point out that the result has been generalized to all planar graphs in the meanwhile. We also consider another drawing style that extends beyond the capabilities of stack layouts called arc diagrams. In contrast to stack layouts, edges in an arc diagram may be drawn above and below the spine and may even intersect the spine once, yielding a so-called biarc. In addition, all edges are intersection-free. We consider a variant called down-up monotone arc diagram where all biarcs must have the same monotone shape. This drawing style has applications in point-set-embeddability problems. We improve the best known upper bound for the number of biarcs in such arc diagrams and present a SAT formulation of the arc diagram drawing problem.

In the third and final part of the thesis, we shift our attention to beyond planar drawings which are motivated by the fact that visualization of nonplanar real-world graphs is necessary in many applications. In particular, we study RAC-k drawings, that is, drawings in which every edge is drawn as a polyline with at most k bends so that all intersections occur at right angles. First, we consider the density of graphs admitting RAC-1 drawings and give a new upper bound that we prove to be tight up to an additive constant. We also show that the graphs that admit simple RAC-1 drawings have slightly smaller edge density and provide a lower bound construction for this restricted scenario. Second, we investigate the area requirement of RAC drawings of dense graphs. Namely, we prove that every graph admits a RAC-3 drawing in cubic area and a RAC-8 drawing in quadratic area. In the case of p-partite graphs we even show how to achieve quadratic area RAC-3 drawings which we prove to not be possible for general graphs.

Finally, we conclude the thesis with a summary of our results and several interesting open research problems.