-
Article
Open AccessUpward Book Embeddability of st-Graphs: Complexity and Algorithms
A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the b...
-
Chapter
10 Reasons to Get Interested in Graph Drawing
This is an invitation to the research area of graph drawing. It encompasses basic research such as graph theory, complexity theory, data structures, and graph algorithms as well as applied research such as sof...
-
Chapter and Conference Paper
Placing Arrows in Directed Graph Drawings
We consider the problem of placing arrow heads in directed graph drawings without them overlap** other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness ...
-
Chapter and Conference Paper
Visibility Representations of Boxes in 2.5 Dimensions
We initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane ...
-
Chapter and Conference Paper
2-Layer Fan-Planarity: From Caterpillar to Stegosaurus
In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are assigned to two distinct ho...
-
Chapter and Conference Paper
Fan-Planar Graphs: Combinatorial Properties and Complexity Results
In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt, who proved that every n-vertex fan-planar draw...
-
Chapter and Conference Paper
Drawing Non-Planar Graphs with Crossing-Free Subgraphs
We initiate the study of the following problem: Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing Γ of G in the plane such that the edges of S are not crossed in Γ?
-
Chapter and Conference Paper
Upward Planarity Testing of Embedded Mixed Graphs
A mixed graph has both directed and undirected edges. We study an upward planarity testing problem for embedded mixed graphs and solve it using Integer Linear Programming. Experiments show the efficiency of our t...
-
Chapter and Conference Paper
Drawing Trees in a Streaming Model
We introduce a data stream model of computation for Graph Drawing, where a source produces a graph one edge at a time. When an edge is produced, it is immediately drawn and its drawing can not be altered. The ...
-
Chapter and Conference Paper
Maximum Upward Planar Subgraphs of Embedded Planar Digraphs
This paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: (i) We prove ...
-
Chapter and Conference Paper
Computing Labeled Orthogonal Drawings
This paper studies the problem of computing labeled orthogonal drawings. A label is modeled as a rectangle of prescribed size and it can be associated with either a vertex or an edge. Several optimization goal...
-
Chapter and Conference Paper
Labeling Heuristics for Orthogonal Drawings
This paper studies the problem of computing an orthogonal drawing of a graph with labels along the edges. Labels are not allowed to overlap with each other or with edges to which they are not assigned. The opt...
