We obtain new parameterized algorithms for the classical problem of determining whether a
directed acyclic graph admits an upward planar drawing. Our results include a new fixed …

Algorithmic extension problems of partial graph representations such as planar graph
drawings or geometric intersection representations are of growing interest in topological …

The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such
that vertices are placed at prescribed y-coordinates (called levels) and such that every edge …

The problem of extending partial geometric graph representations such as plane graphs has
received considerable attention in recent years. In particular, given a graph $ G $, a …

Abstract A simple drawing D (G) of a graph G is one where each pair of edges share at most
one point: either a common endpoint or a proper crossing. An edge e in the complement of …

In extension problems of partial graph drawings one is given an incomplete drawing of an
input graph $ G $ and is asked to complete the drawing while maintaining certain properties …

A hierarchical plane st-graph H can be thought of as a combinatorial description of a planar
drawing Γ of a 2-connected graph G in which each edge is a y-monotone curve and each …

The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such
that vertices are placed at prescribed y-coordinates (called levels) and such that every edge …

Many real-world networks exhibit an inherent clustering structure, which may arise from the
presence of communities inside the network or from semantic affinities among nodes …

In this paper we study the computational complexity of the Upward Planarity Extension
problem, which takes as input an upward planar drawing Γ H of a subgraph H of a directed …