24 Result(s)
within
Carla Binucci
English
-
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 and Conference Paper
Evaluating Animation Parameters for Morphing Edge Drawings
Partial edge drawings (ped) of graphs avoid edge crossings by subdividing each edge into three parts and representing only its stubs, i.e., the parts incident to the end-nodes. The morphing edge drawing model (me...
-
Chapter and Conference Paper
Nonplanar Graph Drawings with k Vertices per Face
The study of nonplanar graph drawings with forbidden or desired crossing configurations has a long tradition in geometric graph theory, and received an increasing attention in the last two decades, under the n...
-
Chapter and Conference Paper
On the Complexity of the Storyplan Problem
Motivated by dynamic graph visualization, we study the problem of representing a graph G in the form of a storyplan, that is, a sequence of frames with the following properties. Each frame is a planar drawing of ...
-
Chapter and Conference Paper
st-Orientations with Few Transitive Edges
The problem of orienting the edges of an undirected graph such that the resulting digraph is acyclic and has a single source s and a single sink t has a long tradition in graph theory and is central to many graph...
-
Chapter and Conference Paper
Min-k-planar Drawings of Graphs
The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of d...
-
Chapter and Conference Paper
Quasi-upward Planar Drawings with Minimum Curve Complexity
This paper studies the problem of computing quasi-upward planar drawings of bimodal plane digraphs with minimum curve complexity, i.e., drawings such that the maximum number of bends per edge is minimized. We ...
-
Chapter and Conference Paper
An Experimental Study of a 1-Planarity Testing and Embedding Algorithm
A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. The 1-planarity testing problem is NP-complete, even for restricted classes of graphs. We present the first general 1-pl...
-
Chapter and Conference Paper
On Turn-Regular Orthogonal Representations
An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that “point to each other” inside a face. For such a repr...
-
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
1-Page and 2-Page Drawings with Bounded Number of Crossings per Edge
A 2-page drawing of a graph is such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line. If all edges are in the same half-plan...
-
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
Quasi-Upward Planar Drawings of Mixed Graphs with Few Bends: Heuristics and Exact Methods
A mixed graph has both directed and undirected edges. We study how to compute a crossing-free drawing of a planar embedded mixed graph, such that it is upward “as much as possible”. Roughly speaking, in an upward...
-
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
Universal Point Subsets for Planar Graphs
A set S of k points in the plane is a universal point subset for a class \({\mathcal G}\) of planar graphs if every gra...
-
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 ...
