### C-planarity of Embedded Cyclic c-Graphs

**2016-02-03**

1602.01346 | cs.CG

We show that c-planarity is solvable in quadratic time for flat clustered
graphs with three clusters if the combinatorial embedding of the underlying
graph is fixed. In simpler graph-theoretical terms our result can be viewed as
follows. Given a graph $G$ with the vertex set partitioned into three parts
embedded on a 2-sphere, our algorithm decides if we can augment $G$ by adding
edges without creating an edge-crossing so that in the resulting spherical
graph the vertices of each part induce a connected sub-graph. We proceed by a
reduction to the problem of testing the existence of a perfect matching in
planar bipartite graphs. We formulate our result in a slightly more general
setting of cyclic clustered graphs, i.e., the simple graph obtained by
contracting each cluster, where we disregard loops and multi-edges, is a cycle.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-02-19**

1802.06579 | cs.CG

We study the problem of convexifying drawings of planar graphs. Given any
planar straight-line drawi… show more

**2018-12-04**

1812.01564 | cs.CG

Let $G$ be a directed graph with $n$ vertices and $m$ edges, embedded on a
surface $S$, possibly wit… show more

**2018-12-11**

1812.04543 | cs.DS

It is well-known that every planar graph has a Tutte path, i.e., a path $P$
such that any component … show more

**2019-03-13**

1903.05363 | cs.CG

We study $c$-crossing-critical graphs, which are the minimal graphs that
require at least $c$ edge-c… show more

**2018-08-31**

1808.10826 | cs.DS

We prove that, given two topologically-equivalent upward planar straight-line
drawings of an $n$-ver… show more

**2019-02-18**

1902.06575 | cs.DS

In this paper we study the computational complexity of the Upward Planarity
Extension problem, which… show more

**2018-10-15**

1810.06625 | cs.DM

We introduce a dynamic version of the NP-hard graph problem Cluster Editing.
The essential point her… show more

**2018-12-11**

1812.04263 | cs.CG

An effective way to reduce clutter in a graph drawing that has (many)
crossings is to group edges in… show more

**2018-10-31**

1810.13297 | cs.DS

In this paper, we introduce and study the multilevel-planarity testing
problem, which is a generaliz… show more

**2017-08-25**

1708.07653 | cs.CG

We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs
that have a drawing in… show more

**2017-02-20**

1702.06163 | cs.CG

Edge bundling is an important concept heavily used for graph visualization
purposes. To enable the c… show more

**2015-10-09**

1510.02659 | cs.CG

Given a planar graph $G$ and a partition of the neighbors of each vertex $v$
in four sets $UR(v)$, $… show more

**2019-06-05**

1906.01904 | math.CO

We study the problem of colouring visibility graphs of polygons. In
particular, for visibility graph… show more

**2019-01-21**

1901.07028 | cs.DM

This note presents several results in graph theory inspired by the author's
work in the proof theory… show more

**2019-03-19**

1903.07966 | cs.CG

We study $k$-page upward book embeddings ($k$UBEs) of $st$-graphs, that is,
book embeddings of singl… show more

**2018-08-22**

1808.07437 | cs.DM

The complexity of deciding whether a clustered graph admits a clustered
planar drawing is a long-sta… show more