ML p(r)ior | C-planarity of Embedded Cyclic c-Graphs

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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2018-02-19

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-03-13

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

Highlights - Most important sentences from the article

2018-08-31

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

Highlights - Most important sentences from the article

2019-02-18

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

Highlights - Most important sentences from the article

2018-10-15

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

Highlights - Most important sentences from the article

2018-12-11

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

Highlights - Most important sentences from the article

2018-10-31

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

Highlights - Most important sentences from the article

2017-08-25

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

Highlights - Most important sentences from the article

2017-02-20

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

Highlights - Most important sentences from the article

2015-10-09

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

Highlights - Most important sentences from the article

2019-06-05

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-03-19

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

Highlights - Most important sentences from the article

2018-08-22

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