\(c\)-planarity of embedded cyclic \(c\)-graphs (Q1693313)

From MaRDI portal
scientific article; zbMATH DE number 6687289
  • C-Planarity of Embedded Cyclic c-Graphs
Language Label Description Also known as
English
\(c\)-planarity of embedded cyclic \(c\)-graphs
scientific article; zbMATH DE number 6687289
  • C-Planarity of Embedded Cyclic c-Graphs

Statements

\(c\)-planarity of embedded cyclic \(c\)-graphs (English)
0 references
C-Planarity of Embedded Cyclic c-Graphs (English)
0 references
0 references
0 references
0 references
12 February 2018
0 references
21 February 2017
0 references
Testing planarity of graphs with additional constrains is a popular topic in graph visualizations. One of these planarity variant is \(c\)-planarity. The article proves 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. The result can be formulated in graph theoretical terms as follows: Given a graph \(G\) with the vertex set partitioned into three parts embedded on a 2-sphere, the algorithm decides if \(G\) can be augmented 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.
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
graph drawing
0 references
\(c\)-planarity
0 references
complexity of decision problem
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references