C-planarity of embedded cyclic c-graphs Conference Paper

Author(s): Fulek, Radoslav
Title: C-planarity of embedded cyclic c-graphs
Title Series: LNCS
Affiliation IST Austria
Abstract: 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.
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 19-21, 2016
Conference Location: Athens, Greece
ISBN: 978-331927260-3
Publisher: Springer  
Date Published: 2016-01-01
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/2007-2013) under REA grant agreement no [291734].
DOI: 10.1007/978-3-319-50106-2_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)
IST Austria Authors
  1. Radoslav Fulek
    14 Fulek
Related IST Austria Work