Publications

Upward Planar Morphs

We prove that, given two topologically equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there …

On Planar Greedy Drawings of 3-Connected Planar Graphs

A graph drawing is greedy if, for every ordered pair of vertices $(x,y)$, there is a path from $x$ to $y$ such that the Euclidean …

Extending Upward Planar Graph Drawings

In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes in input an upward planar …

Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and …

Beyond level planarity: Cyclic, torus, and simultaneous level planarity

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to …

Graph Stories in Small Area

We study the problem of drawing a dynamic graph, where each vertex appears in the graph at a certain time and remains in the graph for …

Computing k-Modal Embeddings of Planar Digraphs

Given a planar digraph $G$ and a positive even integer $k$, an embedding of $G$ in the plane is $k$-modal, if every vertex of $G$ is …

Reaching 3-Connectivity via Edge-edge Additions

Given a graph $G$ and a pair $\langle e’,e’’\rangle$ of distinct edges of $G$, an edge-edge addition on $\langle …

Upward Book Embeddings of st-Graphs

We study k-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic …

Morphing Contact Representations of Graphs

We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, …

How to Morph a Tree on a Small Grid

In this paper, we study planar morphs between straight-line planar grid drawings of trees. A morph consists of a sequence of morphing …

Extending Upward Planar Graph Drawings

In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes in input an upward planar …

Planarity of Streamed Graphs

In this research we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream …

Clustered Planarity with Pipes

In this paper we study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into …

C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width

For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks …

Analogies between the Crossing Number and the Tangle Crossing Number

Tanglegrams are special graphs that consist of a pair of rooted binary trees with the same number of leaves, and a perfect matching …

3-coloring arrangements of line segments with 4 slopes is hard

In a paper first appeared at SODA ’04, Eppstein proved that testing the $3$-colorability of arrangements of line segments is an …

Upward Planar Morphs

We prove that, given two topologically equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there …

Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity

The C-Planarity problem asks for a drawing of a clustered graph, i.e., a graph whose vertices belong to properly nested clusters, in …

Approximation Algorithms for Facial Cycles in Planar Embeddings

Consider the following combinatorial problem$:$ Given a planar graph $G$ and a set of simple cycles $\mathcal C$ in $G$, find a planar …

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

Given a planar graph $G(V,E)$ and a partition of the neighbors of each vertex $v \in V$ in four sets $\overset{\nwarrow}{v}$, …

Drawing Planar Graphs with Many Collinear Vertices

Consider the following problem$:$ Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line …

Computing NodeTrix Representations of Clustered Graphs

NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and …

On Planar Greedy Drawings of 3-Connected Planar Graphs

A graph drawing is greedy if, for every ordered pair of vertices $(x,y)$, there is a path from $x$ to $y$ such that the Euclidean …

How to Morph Planar Graph Drawings

Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show …

Planar L-Drawings of Directed Graphs

We study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these …

Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs

A square-contact representation of a planar graph $G=(V,E)$ maps the vertices in $V$ to interior disjoint axis-aligned squares in the …

Strip Planarity Testing for Embedded Planar Graphs

In this paper we introduce and study the Strip Planarity Testing problem, which takes as an input a planar graph $G(V,E)$ and a …

Intersection-Link Representations of Graphs

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which …

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

Given a planar graph $G(V,E)$ and a partition of the neighbors of each vertex $v \in V$ in four sets $\overset{\nwarrow}{v}$, …

Simultaneous Orthogonal Planarity

We introduce and study the OrthoSEFE-$k$ problem$:$ Given~$k$ planar graphs each with maximum degree 4 and the same vertex set, is …

L-Drawings of Directed Graphs

We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal …

Drawing Planar Graphs with Many Collinear Vertices

Consider the following problem$:$ Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line …

Computing NodeTrix Representations of Clustered Graphs

NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and …

Clustered Planarity with Pipes

In this paper we study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into …

Beyond Level Planarity

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to …

SEFE = C-Planarity?

In this article, we deepen the understanding of the connection between two long-standing graph drawing open problems, Simultaneous …

Optimal Morphs of Convex Drawings

We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of …

Planar Graphs with Vertices in Prescribed Regions: models, algorithms, and complexity

The volume and the complexity of structured relational information created and handled by modern information systems has drastically …

Planarity of Streamed Graphs

In this research we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream …

Intersection-Link Representations of Graphs

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which …

Drawing Georeferenced Graphs - Combining Graph Drawing and Geographic Data

We consider the task of visually exploring relationships (such as established connections, similarity, reachability, etc) among a set …

Relaxing the constraints of clustered planarity

In a drawing of a clustered graph vertices and edges are drawn as points and curves, respectively, while clusters are represented by …

Advancements on SEFE and Partitioned Book Embedding problems

In this work we investigate the complexity of some combinatorial problems related to the Simultaneous Embedding with Fixed Edges (SEFE) …

On Some NP-complete SEFE Problems

In this work we investigate the complexity of some combinatorial problems related to the Simultaneous Embedding with Fixed Edges (SEFE) …

Morphing Planar Graph Drawings Optimally

We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any $n$-vertex plane graph in …

Planar Embeddings with Small and Uniform Faces

Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and …

Anchored Drawings of Planar Graphs

In this paper we study the ANCHORED GRAPH DRAWING (AGD) problem$:$ Given a planar graph $G$, an initial placement for its vertices, and …

Visual discovery of the correlation between BGP routing and round-trip delay active measurements

Inter-domain routing data and Internet active probing measurements are two types of information commonly available in huge datasets and …

Strip Planarity Testing

In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph $G(V,E)$ and a …

Drawing Graphs on a Smartphone

We present a system for the visualization of information modeled in terms of a graph on a smartphone. First, we show the adopted …

Drawing Graphs on a Smartphone

We present a system for the visualization of information modeled in terms of a graph on a smartphone. First, we show the adopted …