---
_id: '1165'
abstract:
- lang: eng
  text: 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.
acknowledgement: "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].\r\nI
  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."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
citation:
  ama: 'Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer;
    2016:94-106. doi:<a href="https://doi.org/10.1007/978-3-319-50106-2_8">10.1007/978-3-319-50106-2_8</a>'
  apa: 'Fulek, R. (2016). C-planarity of embedded cyclic c-graphs (Vol. 9801, pp.
    94–106). Presented at the GD: Graph Drawing and Network Visualization, Athens,
    Greece: Springer. <a href="https://doi.org/10.1007/978-3-319-50106-2_8">https://doi.org/10.1007/978-3-319-50106-2_8</a>'
  chicago: Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106.
    Springer, 2016. <a href="https://doi.org/10.1007/978-3-319-50106-2_8">https://doi.org/10.1007/978-3-319-50106-2_8</a>.
  ieee: 'R. Fulek, “C-planarity of embedded cyclic c-graphs,” presented at the GD:
    Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp.
    94–106.'
  ista: 'Fulek R. 2016. C-planarity of embedded cyclic c-graphs. GD: Graph Drawing
    and Network Visualization, LNCS, vol. 9801, 94–106.'
  mla: Fulek, Radoslav. <i>C-Planarity of Embedded Cyclic c-Graphs</i>. Vol. 9801,
    Springer, 2016, pp. 94–106, doi:<a href="https://doi.org/10.1007/978-3-319-50106-2_8">10.1007/978-3-319-50106-2_8</a>.
  short: R. Fulek, in:, Springer, 2016, pp. 94–106.
conference:
  end_date: 2016-09-21
  location: Athens, Greece
  name: 'GD: Graph Drawing and Network Visualization'
  start_date: 2016-09-19
date_created: 2018-12-11T11:50:30Z
date_published: 2016-12-08T00:00:00Z
date_updated: 2025-09-22T09:54:03Z
day: '08'
department:
- _id: UlWa
doi: 10.1007/978-3-319-50106-2_8
ec_funded: 1
external_id:
  arxiv:
  - '1602.01346'
  isi:
  - '000405478500008'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1602.01346
month: '12'
oa: 1
oa_version: Preprint
page: 94 - 106
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6192'
quality_controlled: '1'
related_material:
  record:
  - id: '794'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: C-planarity of embedded cyclic c-graphs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: '9801 '
year: '2016'
...