Author(s):

Fulek, Radoslav

Title: 
Cplanarity of embedded cyclic cgraphs

Title Series: 
LNCS

Affiliation 
IST Austria 
Abstract: 
We show that cplanarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graphtheoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2sphere, our algorithm decides if we can augment G by adding edges without creating an edgecrossing so that in the resulting spherical graph the vertices of each part induce a connected subgraph. 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 multiedges, is a cycle.

Keywords: 
visualization; bipartite graphs; Perfect matchings; Engineering controlled terms: drawing (graphics); graphic methods; clustered graph; edge crossing; quadratic time; theoretical terms; underlying graphs; vertex set; engineering main heading: graph theory

Conference Title:

GD: Graph Drawing and Network Visualization

Volume: 
9801

Conference Dates:

September 1921, 2016

Conference Location:

Athens, Greece

ISBN:

9783319272603

Publisher:

Springer

Date Published:

20160101

Start Page: 
94

End Page:

106

Sponsor: 
R. Fulek—The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/20072013) under REA grant agreement no [291734].

URL: 

DOI: 
10.1007/9783319501062_8

Notes: 
I would like to thank Jan Kynčl and Dömötör Pálvölgyi for many comments and suggestions that helped to improve the presentation of the result.

Open access: 
yes (repository) 