research
∙
07/25/2023
Upward Planarity Testing of Biconnected Outerplanar DAGs Solves Partition
We show an O(n)-time reduction from the problem of testing whether a mul...
share
research
∙
10/11/2022
Morphing Planar Graph Drawings Through 3D
In this paper, we investigate crossing-free 3D morphs between planar str...
research
∙
08/30/2022
Unit-length Rectangular Drawings of Graphs
A rectangular drawing of a planar graph G is a planar drawing of G in wh...
research
∙
08/29/2022
Recognizing DAGs with Page-Number 2 is NP-complete
The page-number of a directed acyclic graph (a DAG, for short) is the mi...
research
∙
08/26/2022
Testing Upward Planarity of Partial 2-Trees
We present an O(n^2)-time algorithm to test whether an n-vertex directed...
research
∙
03/10/2022
Parameterized Algorithms for Upward Planarity
We obtain new parameterized algorithms for the classical problem of dete...
research
∙
08/28/2021
Planar Straight-line Realizations of 2-Trees with Prescribed Edge Lengths
We study a classic problem introduced thirty years ago by Eades and Worm...
research
∙
08/21/2021
From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
The algorithm of Tutte for constructing convex planar straight-line draw...
research
∙
11/04/2020
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
Given a bipartite graph G=(V_b,V_r,E), the 2-Level Quasi-Planarity probl...
research
∙
08/21/2020
Schematic Representation of Large Biconnected Graphs
Suppose that a biconnected graph is given, consisting of a large compone...
research
∙
06/19/2020
Universal Geometric Graphs
We introduce and study the problem of constructing geometric graphs that...
research
∙
06/12/2020
Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
We show how to test in linear time whether an outerplanar graph admits a...
research
∙
03/01/2020
On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs
In this paper we study the area requirements of planar greedy drawings o...
research
∙
02/13/2020
Drawing Graphs as Spanners
We study the problem of embedding graphs in the plane as good geometric ...
research
∙
09/16/2019
How to Morph a Tree on a Small Grid
In this paper we study planar morphs between straight-line planar grid d...
research
∙
08/25/2019
Graph Stories in Small Area
We study the problem of drawing a dynamic graph, where each vertex appea...
research
∙
08/09/2019
On the Edge-Length Ratio of Planar Graphs
The edge-length ratio of a straight-line drawing of a graph is the ratio...
research
∙
02/28/2019
On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees
In this paper, we study the area requirements of planar straight-line or...
research
∙
02/18/2019
Extending Upward Planar Graph Drawings
In this paper we study the computational complexity of the Upward Planar...
research
∙
08/31/2018
Upward Planar Morphs
We prove that, given two topologically-equivalent upward planar straight...
research
∙
08/31/2018
Pole Dancing: 3D Morphs for Tree Drawings
We study the question whether a crossing-free 3D morph between two strai...
research
∙
09/13/2017