2026-09-18T17:51:46Zhttps://publikationen.uni-tuebingen.de/oai/requestoai:publikationen.uni-tuebingen.de:10900/1088472020-11-04T09:46:41Zcom_10900_42126col_10900_42133
Publikationssystem UB Tuebingen
advisor
Kaufmann, Michael (Prof. Dr.)
author
Förster, Henry
2020-11-02T09:29:45Z
2020-11-02
1737746220
http://hdl.handle.net/10900/108847
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.
en
ubt-podok
Graph Drawing Beyond the Beaten Tracks
PhDThesis
URL
https://publikationen.uni-tuebingen.de/xmlui/bitstream/10900/108847/2/paper.pdf
File
MD5
ed3a81f411ad6dea35a52eecec7a08bb
17032808
application/pdf
paper.pdf
URL
https://publikationen.uni-tuebingen.de/xmlui/bitstream/10900/108847/4/paper.pdf.txt
File
MD5
ff90c2732df32b6467faf31ff063a7d4
468939
text/plain
paper.pdf.txt