Upward Planarity

Upward Planar Morphs

We prove that, given two topologically equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there always exists a morph between them such that all the drawings of the morph are upward planar and straight-line. Such a …

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 drawing $\Gamma_H$ of a subgraph $H$ of a directed graph $G$ and asks whether $\Gamma_H$ can be extended to an upward …

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 drawing $\Gamma_H$ of a subgraph $H$ of a directed graph $G$ and asks whether $\Gamma_H$ can be extended to an upward …

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 steps, where in a morphing step vertices move along straight-line trajectories at constant speed. We show how to …

Upward Planar Morphs

We prove that, given two topologically equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there always exists a morph between them such that all the drawings of the morph are upward planar and straight-line. Such a …

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}$, $\overset{\nearrow}{v}$, $\overset{\swarrow}{v}$, and $\overset{\searrow}{v}$, the problem Windrose Planarity asks to decide …

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 function $\gamma:V \rightarrow \{1,2,\dots,k\}$ and asks whether a planar drawing of $G$ exists such that each edge is …

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}$, $\overset{\nearrow}{v}$, $\overset{\swarrow}{v}$, and $\overset{\searrow}{v}$, the problem Windrose Planarity asks to decide …

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 function $\gamma:V \rightarrow \{1,2,\dots,k\}$ and asks whether a planar drawing of $G$ exists such that each edge is …