C-Planarity

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 whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region …

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 pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances …

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 which each cluster is represented by a simple closed region with no edge- edge crossings, no region-region crossings, …

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 …

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 pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances …

SEFE = C-Planarity?

In this article, we deepen the understanding of the connection between two long-standing graph drawing open problems, Simultaneous Embedding with Fixed Edges (SEFE-2) and Clustered Planarity (C-Planarity). Given two planar graphs on the same set of …

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex $u$ is represented by a geometric object $R(u)$ and in which each edge $(u,v)$ is represented by the …

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 simple closed regions. A drawing of a clustered graph is c-planar if it has no edge-edge, edge-region, or …

The Importance of Being Proper - (In Clustered-Level Planarity and T-Level Planarity)

In this paper we study two problems related to the drawing of level graphs, that is, $T$-Level Planarity and Clustered-Level Planarity. We show that both problems are $\mathcal{NP}$-complete in the general case and that they become polynomial-time …

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 a distance $d$, produce a planar straight-line drawing of $G$ such that each vertex is at distance at most $d$ …