C-Planarity of Embedded Cyclic c-Graphs

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.

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

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Testing planarity of graphs with additional constraints is a popular theme in the area of graph visualizations. One of most the prominent such planarity variants, c-planarity, raised in 1995 by Feng, Cohen and Eades [12, 13] asks for a given planar graph G equipped with a hierarchical structure on its vertex set, i.e., clusters, to decide if a planar embedding G with the following property exists: the vertices in each cluster are drawn inside a disc so that the discs form a laminar set family corresponding to the given hierarchical structure and the embedding has the least possible number of edge-crossings with the boundaries of the discs. Shortly after, several groups of researchers tried to settle the main open problem formulated by Feng et al. asking to decide its complexity status, i.e., either provide a polynomial/sub-exponential-time algorithm for c-planarity or show its NP-hardness. First, Biedl [5] gave a polynomial-time algorithm for c-planarity with two clusters. A different approach for two clusters was considered by Hong and Nagamochi [19] and quite recently in [15]. The result also follows from a work by Gutwenger et al. [17]. Beyond two clusters a polynomial time algorithm for c-planarity was obtained only in special cases, e.g., [8, 16, 17, 20, 21], and most recently in [6, 7]. Cortese et al. [9] shows that c-planarity is solvable in polynomial time if the underlying graph is a cycle and the number of clusters is at most three.

In the present work we generalize the result of Cortese et al. to the class of all planar graphs with a given combinatorial embedding. In a recent pre-print [14] we established a strengthening for trees, where we do not fix the embedding. In the general case (including already the case of three clusters) of so-called flat clustered graphs a similar result was obtained only in very limited cases. Specifically, either when every face of G is incident to at most five vertices [10, 15], or when there exist at most two vertices of a cluster incident to a single face [7]. We remark that the techniques of the previously mentioned papers do not give a polynomial-time algorithm for the case of three clusters, and also do not seem to be adaptable to this setting. Our result and the technique used to achieve it suggest that, for a fairly general class of clustered graphs, c-planarity could be tractable/solvable in sub-exponential time at least with a fixed combinatorial embedding.

Notation. Let $G=(V,E)$ denote a connected planar graph possibly with multi-edges. For standard graph theoretical definitions such as path, cycle, walk etc., we refer reader to [11, Sect. 1]. A drawing of G is a representation of G in the plane where every vertex in V is represented by a unique point and every edge $e=uv$ in E is represented by a Jordan arc joining the two points that represent u and v. We assume that in a drawing no edge passes through a vertex, no two edges touch and every pair of edges cross in finitely many points. An embedding of G is an edge-crossing free drawing. If it leads to no confusion, we do not distinguish between a vertex or an edge and its representation in the drawing and we use the words “vertex” and “edge” in both contexts. A face in an embedding is a connected component of the complement of the embedding of G (as a topological space) in the plane. The facial walk of f is the closed walk in G with a fixed orientation that we obtain by traversing the boundary of f counter-clockwise. In order to simplify the notation we sometimes denote the facial walk of a face f by f. A pair of consecutive edges e and $e'$ in a facial walk f creates a wedge incident to f at their common vertex. A vertex or an edge is incident to a face f, if it appears on its facial walk. The rotation at a vertex is the counter-clockwise cyclic order of the end pieces of its incident edges in a drawing of G. An embedding of G is up to an isotopy and the choice of an outer (unbounded) face described by the rotations at its vertices. We call such a description of an embedding of G a combinatorial embedding. Remaining faces are inner faces. The interior and exterior of a cycle in an embedded graph is the bounded and unbounded, respectively, connected component of its complement in the plane. Similarly, the interior and exterior of an inner face in an embedded graph is the bounded and unbounded, respectively, connected component of the complement of its facial walk in the plane, and vice-versa for the outer face. When talking about interior/exterior or area of a cycle in a graph G with a combinatorial embedding and a designated outer face we mean it with respect to an embedding in the isotopy class that G defines. For $V'\subseteq V$ we denote by $G[V']$ the sub-graph of G induced by $V'$.

A flat clustered graph, shortly c-graph, is a pair (G, T), where $G=(V,E)$ is a graph and $T=\{V_0, \ldots , V_{c-1}\}$, $\biguplus _i V_i=V$, is a partition of the vertex set into clusters. See Fig. 1 for an illustration. A c-graph (G, T) is clustered planar (or briefly c-planar) if G has an embedding in the plane such that (i) for every $V_i\in T$ there is a topological disc $D(V_i)$, where $\mathrm {interior}(D(V_i))\cap \mathrm {interior} (D(V_j))=\emptyset$, if $i\not =j$, containing all the vertices of $V_i$ in its interior, and (ii) every edge of G intersects the boundary of $D(V_i)$ at most once for every $D(V_i)$. A c-graph (G, T) with a given combinatorial embedding of G is c-planar if additionally the embedding is combinatorially described as given. A clustered drawing and embedding of a flat clustered graph (G, T) is a drawing and embedding, respectively, of G satisfying (i) and (ii). In 1995 Feng, Cohen and Eades [12, 13] introduced the notion of clustered planarity for clustered graphs, shortly c-planarity, (using, a more general, hierarchical clustering) as a natural generalization of graph planarity. (Under a different name Lengauer [22] studied a similar concept in 1989.)

Fig. 1.

A c-graph that is not c-planar (left); and a c-planar c-graph (right).

By slightly abusing the notation for the rest of the paper G denotes a flat c-graph $(G,T)=(V_0 \uplus V_1 \uplus \ldots \uplus V_{c-1}, E)$ with c clusters $V_0,V_1,\ldots$ and $V_{c-1}$, and a given combinatorial embedding, and we assume that G is cyclic [15, Sect. 6]. Thus, every $e=uv$ of G is such that $u\in V_i$ and $v\in V_j$ where $j-i \mod c \le 1$ and for every i there exists an edge in G between $V_i$ and $V_{i+1 \mod c}$. In the case of three clusters, the first condition is redundant. If the second condition is violated, the problem was essentially solved for three clusters as discussed in Sect. 2.3. We assume that G is connected, since in the problem that we are studying, the connected components of G can be treated separately. Indeed, without loss of generality we assume throughout the paper that in a clustered embedding of G the clusters are unbounded wedges defined by pairs of rays emanating from the origin (see Fig. 2a) that is disjoint from all the edges. We call such a clustered drawing a fan drawing.

Fig. 2.

(a) A clustered graph $G=(V_0 \uplus V_1 \uplus V_2,E)$ with clusters represented by wedges bounded by rays meeting at the origin. The highlighted wedge at u is concave and at v convex. (b) A semi-simple face f and the outer face $f_o$ with an incident concave wedge.

Thus, a connected component in a clustered embedding can be drawn so that it is disjoint from a ball B centered at the origin of radius $\epsilon >0$ for any $\epsilon$. The rest of the graph is then embedded inductively inside B. The aim of the present work is to prove the following.

Theorem 1

There exists a quadratic-time algorithm in |V(G)| to test if a cyclic c-graph (G, T) is c-planar.

Further Research Directions. We think that our technique should be extendable by means of Euler’s formula to resolve the c-planarity in more general situations than the one treated in the present paper. In particular, we suspect that the technique should yield a generalization of the characterization of strip planar clustered graphs [14, Sect. 5]. That would allow us to work with graphs without a fixed embedding. We mention that the tractability in a special case of our problem known as cyclic level planarity, when the embedding is not fixed, follows from a recent work of Angelini et al. [2].

Organization. In Sect. 2 we introduce concepts used in the proof of our result. We give an outline of our approach in Sect. 2.1. A more detailed description and a proof of correctness of our algorithm is in Sect. 3.

2 Preliminaries

2.1 Outline of the Approach

By [13, Theorem 1] deciding c-planarity of instances G in which all $G[V_i]$’s are connected amounts to checking if an outer face of G can be chosen so that every $V_i$ is embedded in the outer face of $G[V\setminus V_i]$. On the other hand, once we have a clustered embedding of G we can augment G by adding edges drawn inside clusters without creating an edge-crossing so that clusters become connected. These observations suggest that c-planarity of G could be viewed as a connectivity augmentation problem, for example as in [7, 15], in which we want to decide if it is possible to make clusters connected while maintaining the planarity of G. One minor problem with this viewpoint is the fact that if G is c-planar we do not allow a cluster $V_i$ to induce a cycle such that clusters $V_j$ and $V_{j'}$, $i\not =j,j'$, are drawn on its opposite sides. However, this cannot happen if G is cyclic. Following the above line of thought our algorithm tries to augment G by subdividing its faces with paths and edges. We proceed in two steps. In the first step, Sect. 3.2, we either detect that G is not c-planar or similarly as in [1] and [14] by turning clusters into independent sets and adding certain paths we normalize the instance. In the second step, Sect. 3.1, we decide if the normalized instance can be further augmented by edges as desired.

In order to prove the correctness of the second step of the algorithm we use the notion of the winding number $\mathrm {wn}(W)\in \mathbb {Z}$ of a walk W of G, as defined in Sect. 2.3. The parameter $\mathrm {wn}(W)$ says how many times and in which sense a walk W of G winds around the origin in a clustered drawing of G. Thus, G is not c-planar if there exists a face f such that for its facial walk $|\mathrm {wn}(f)|>1$ or if there exists at least two inner faces f with $|\mathrm {wn}(f)|>0$. However, it can be easily seen that this necessary condition of c-planarity is not sufficient except when G is a cycle [9]. The necessary condition allows us to reduce the c-planarity testing problem of a normalized instance to the problem of finding a perfect matching in an auxiliary face-vertex incidence graph which is polynomially solvable. The novelty of our work lies in the use of the winding number in the context of connectivity augmentation guided by the flow and matching in the auxiliary face-vertex incidence graph à la [1, 14], respectively.

We remark that the approach of [1] via a variant of upward embeddings for directed graphs in our settings has several problems that seem quite hard to overcome, the main one being the fact that the result of Bertolazzi et al. [4] does not extend, at least not in a natural way, to the drawings on the rolling cylinder, see e.g., Auer et al. [3] for the definition of these drawings. We are not aware of a polynomial-time algorithm for the corresponding problem, nor a corresponding NP-hardness result, and find the corresponding algorithmic question interesting and related to our problem.

2.2 Winding Number

We define the winding number $\mathrm {wn}(W)$ of a closed oriented walk W in a drawing disjoint from the origin of a graph G (possibly with crossings). In what follows facial walks are understood with the orientations as in an embedding of G with the given rotations and a face $f_o$ being a designated outer face. By viewing a closed walk W in the drawing as a continuous function w from the unit circle $S^1$ to $\mathbb {R}^2\setminus \mathbf{0}$, the winding number $\mathrm {wn}(W)\in \mathbb {Z}$ corresponds to the element of the fundamental group of $S^1$ [18, Chap. 1.1] represented by $\frac{w(x)}{||w(x)||_2}$. Let $W_1$ and $W_2$ denote a pair of oriented closed walks meeting in a vertex v. Let W denote the closed oriented walk from v to v obtained by concatenating $W_1$ and $W_2$. By the definition of $\mathrm {wn}$ we have $\mathrm {wn}(W)=\mathrm {wn}(W_1)+\mathrm {wn}(W_2)$. Let $f_1$ and $f_2$, $f_o\not = f_1, f_2$, denote a pair of faces of G whose walks intersect in a single walk. Let $G'$ denote a graph we get from G by deleting edges incident to both $f_1$ and $f_2$. Let f denote the new face thereby obtained. Since $f_1$ and $f_2$ intersect in a single walk, the boundary of f is connected. In the drawing of $G'$ inherited from the drawing of G we have $\mathrm {wn}(f)=\mathrm {wn}(f_1)+\mathrm {wn}(f_2)$, since common edges of $f_1$ and $f_2$ are traversed in opposite directions by $f_1$ and $f_2$. A face or a vertex is in the interior of a closed walk W in G if it is in the interior of a cycle induced by the edges of W in an embedding of G with the given rotations and $f_o$ as the outer face. The previous observation is easily generalized by a simple inductive argument as follows

$\mathbf{(*)} \ \ \ \ \sum _f \mathrm {wn}(f)=\mathrm {wn}(W)$

where we sum over all faces f of G in the interior of the closed walk W in G. In particular, $\sum _f \mathrm {wn}(f)=\mathrm {wn}(f_o)$, where we sum over all faces $f\not =f_o$ of G.

2.3 Labeling Vertices

Let $\gamma :V \rightarrow \{0,1,\ldots c-1\}$ be a labeling of the vertices V by integers such that $\gamma (v) = i$ if $v\in V_i$. Let W denote an oriented closed walk in a clustered drawing of G. We put $\mathrm {height}(W)= \sum _{{v'u'}\in E(W)} g(\gamma (u')-\gamma (v'))$, where $g(0)=0, \ g(1)=g(1-c)=1$ and $g(c-1)=g(-1)=-1$. We have the following.

Lemma 1

For a walk W in a fan drawing of G we have $\mathrm {wn}(W)=\mathrm {height}(W)/c$.

Proof

The number of times the walk W crosses the ray between $V_i$ and $V_{i+1 \mod c}$ from right to left w.r.t. to the direction of the ray is $\mathrm {wn}_i^+(W)=\sum _{{v'u'}} g(\gamma (u')-\gamma (v'))$, where we sum over the edges $v'u'$ in the walk W, where $v'\in V_i$ immediately precedes $u'\in V_{i+1 \mod c}$ in the walk. Similarly, we define

$\mathrm {wn}_i^-(W)=\sum _{{v'u'}} g(\gamma (u')-\gamma (v'))$, where we sum over the edges $v'u'$ in W, where $v'\in V_{i+1 \mod c}$ immediately precedes $u'\in V_{i}$ in the walk. We have, $\mathrm {wn}(W) = \mathrm {wn}_i^+(W) + \mathrm {wn}_i^-(W)$ which in turn implies $c\cdot \mathrm {wn}(W) = \sum _{i} (\mathrm {wn}_i^+(W) + \mathrm {wn}_i^-(W))=\mathrm {height}(W)$.    $\blacksquare$

By the previous lemma $\mathrm {wn}(W)$ is determined already by the c-graph G and is the same in all clustered drawings of G, and hence, putting $\mathrm {wn}(W):=\mathrm {height}(W)/c$, for a walk W with a fixed orientation, allows us to speak about $\mathrm {wn}(W)$ without referring to a particular drawing of G. Thus, $\mathrm {wn}(W)$ tells us the winding number of W in any clustered drawing. By Jordan-Schönflies theorem G the following holds.

Lemma 2

G is not c-planar if there exists a face f such that $|\mathrm {wn}(f)|>1$ or if there exists more than one inner face $f'$ with $|\mathrm {wn}(f')|=1$.

Proof

In a crossing free drawing $|\mathrm {wn}(f)|\le 1$ for every face f. If $|\mathrm {wn}(f')|=1$ the origin $\mathbf{0}$ lies in the interior of $f'$ since otherwise the facial walk is null-homotopic, i.e., homotopic to a constant map, in $\mathbb {R}^2\setminus \mathbf{0}$ (contradiction). However, interiors of faces are disjoint.    $\blacksquare$

If $\mathrm {wn}(f)=0$ for all faces f, [14, Lemma 1.2] extends easily to this case, reducing the problem to the work of Angelini et al. [1]. Thus, by Lemma 2 and for the sake of simplicity of the presentation, throughout the paper we assume that there exists a pair of faces $f_o,f_o'$, $\mathrm {wn}(f_o)=\mathrm {wn}(f_o')\not =0$ (by $(*)$ there cannot be just one such face) one of which, let’s say $f_o$, we designate as an outer face. The roles of $f_o$ and $f_o'$ are, in fact, interchangeable. Also such a restriction is by no means crucial in our problem, and alternatively, it is always possible to choose and subdivide the outer face in the normalized instance (defined later) by a path so that the restriction is satisfied.

Viewing a facial walk f as a sequence of vertices and edges $w_0e_0w_1e_2\ldots e_mw_m$, where $e_{i-1}=w_{i-1}w_i$, let $V_f$ be the set $\{w_0,\ldots , w_m\}$ of vertex occurrences along f. We treat $V_f$ also as a multi-set of vertices, and thus, $\gamma$ is defined on its elements. Let $\gamma _f:V_f \rightarrow \mathbb {N}$, for $f\not =f_o,f_o'$, be a labeling of the elements of $V_f$ by integers defined as follows. We mark all the vertex occurrences in $V_f$ as unprocessed. We pick an arbitrary vertex occurrence $v\in V_f$, set $\gamma _f(v):=\gamma (v)$ and mark v as processed. We repeatedly pick an unprocessed vertex occurrence $u\in V_f$ that has its predecessor or successor v along the boundary walk of f in $V_f$ processed. We put $\gamma _f(u):=\gamma _f(v)+g(\gamma (u)-\gamma (v))$. Intuitively, $\gamma _f$ records the distance in terms of “winding around origin” of vertex occurrences along the boundary walk of f from a single chosen vertex occurrence. Since $\mathrm {wn}(f)=0$ the function $\gamma _f(u)$ is completely determined by the choice of the first occurrence of a vertex we processed. This choice is irrelevant for our use of $\gamma _f$ as we see later. Also notice that $\gamma (v) = \gamma _f(v) \mod c$ for all vertices incident to f.

A normalized instance allows only the faces of the types defined next. An element v in $V_f$ is a local minimum (maximum) of a face f if in the facial walk f the value of $\gamma (v)$ is not bigger (not smaller) with respect to the relation $0<1<\ldots<c-1<0$ than the value of its successor and predecessor. A walk W in G is (strictly) monotone with respect to $\gamma$ if the labels of the occurrences of vertices on W form a (strictly) monotone sequence with respect to the relation $0<1<\ldots<c-1<0$ when ordered in the correspondence with their appearance on W. The face f is simple if f has at most one local minimum. It follows that a simple face f has also at most one local maximum. The inner face $f\not =f_o'$ is semi-simple if f has exactly two local minima and maxima and these minima and maxima, respectively, have the same $\gamma _f$ value.

3 Algorithm

A cyclic c-graph G is normalized if

• (i) G is connected;

• (ii) each cluster $V_i$ induces an independent set; and

• (iii) each face of G is simple or semi-simple, and $f_o$ and $f_o'$ are both simple.

Suppose that (i)–(iii) are satisfied. By (ii) we put directions on all the edges in G as follows. Let $\overrightarrow{G}$ denote the directed c-graph obtained from G by orienting every edge uv from the vertex with the smaller label $\min (\gamma (u), \gamma (v))$ to the vertex with the bigger label $\max (\gamma (u), \gamma (v))$ with respect to the relation $0<1<\ldots< c-1<0$. A sink and source of $\overrightarrow{G}$ is a vertex with no outgoing and incoming, respectively, edges.

Let e denote an edge of G not contained in a single cluster. Given a clustered embedding $\mathcal {D}$ of G let $\mathbf{p_{e}}:=\mathbf{p_{e}}(\mathcal {D})$ denote the intersection point of e with a ray separating a pair of clusters. Let $e_0,\ldots ,e_{k-1}$ be the edges incident to a sink or source u. By Jordan curve theorem it is not hard to see that (i)–(iii) imply that a clustered embedding $\mathcal {D}$ of G is “combinatorially” determined once we order the set of intersection points $\mathbf{p_{e_0}}, \ldots , \mathbf{p_{e_{k-1}}}$ along rays separating clusters for every sink and sources u in G. Moreover, the set of intersection points corresponding to a sink or source u admits in an embedding only orders that are cyclic shifts of one another, since we have the rotations at vertices of G fixed. The wedge in $\mathcal {D}$ formed by a pair of edges $e_i$ and $e_{i+1}$ incident to a face f at its local extreme u is concave (see Fig. 2a for an illustration) if u is a sink or source of $\overrightarrow{G}$ and the line segment $\mathbf{p_{e_i}}{} \mathbf{p_{e_{i+1}}}$ contains all the other points $\mathbf{p_{e_j}}$ or in other words the order of intersection points corresponding to u is $\mathbf{p_{e_{i+1}},p_{e_{i+2}}, \ldots , p_{e_{k-1}},p_{e_{0}}, \ldots , p_{e_i}}$. A non-concave wedge is convex. Note that in $\mathcal {D}$ every sink or source is incident to exactly one concave wedge that in turn determines the order of intersection points. Thus, combinatorially $\mathcal {D}$ is also determined by a prescription of concave wedges at sink and sources.

Let S be the set of sinks and sources of $\overrightarrow{G}$. Let F denote the union of the set of semi-simple faces of G with a subset of $\{f_o,f_o'\}$ containing faces incident to a sink and a source. We construct a planar bipartite graph $I=(S\cup F, E(I))$ with parts S and F, where $s\in S$ and $f\in F$ is joined by an edge if s is incident to f. Given that (i)–(iii) are satisfied, the existence of a perfect matching M in I is a necessary condition for G being c-planar. Indeed, as we just said, in a clustered embedding, each source or sink has exactly one of its wedges concave. On the other hand, by Jordan curve theorem it can be easily checked that in the clustered embedding

• (A) every semi-simple face is incident to exactly one concave wedge

• (B) faces $f_o$ and $f_o'$ are incident to one concave wedge if they are incident to a sink and source, and

• (C) all the other faces are not incident to any concave wedges at the minimum and maximum.

This is fairly easy to see if G is vertex two-connected, see Fig. 2b for an illustration. The cycle C corresponding to a closed walk is obtained by traversing the walk and introducing a new vertex for each vertex occurrence in the walk. For a face f incident to cut-vertices, (A)–(C) follows by considering the cycle corresponding to the facial walk of f (treated as a face) embedded in a close vicinity of the boundary of f. Thus, a desired matching M is obtained by matching each source or sink with the face incident to its concave wedge.

We show in Sect. 3.1 that if M exists G is c-planar by augmenting G with edges as described in Sect. 2.1. Testing the existence, but even counting perfect matchings in a planar bipartite graph can be carried out in a polynomial time [23, Sect. 8].

The running time of our algorithm is $O(|V|^2)$ since finding the perfect matching can be done in $O(|V|^2)$ time, due to $|E(I)|=O(|V|)$, and the pre-processing step including the construction of I and the normalization will be easily seen to have this time complexity. Also computing the winding number for all the faces can be performed in a linear time by Lemma 1. First, we explain and prove the correctness of the algorithm for instances satisfying (i)–(iii). In Sect. 3.2, we show a polynomial-time reduction of the general case to instances satisfying (i)–(iii). We often use Jordan–Schönflies theorem without explicitly mentioning it.

Fig. 3.

Subdividing a semi-simple face (left). Subdividing a simple face $f_o'$ (right).

3.1 Constructing a Clustered Embedding

Given a normalized instance G and a matching M between sources and sinks in S, and faces in F of G we construct a clustered embedding of G as follows. Recall that we assume that G does not have a face f with $|\mathrm {wn}(f)|>0$ besides $f_o$ and $f_o'$. We start with $\overrightarrow{G}$ defined above and add edges to it thereby eliminating all the sinks and sources, see Fig. 3. Let $u\in S$ be a source matched in M with f. If f is a semi-simple inner face let $u'$ denote another local minimum incident to f. We add to $\overrightarrow{G}$ an edge $\overrightarrow{u'u}$ embedded in the interior of f. If $f=f_o$ or $f=f_o'$ we join u by $\overrightarrow{u'u}$ with the vertex in the same cluster $u'$ so that we subdivide f into two simple faces $f'$ and $f''$ such that $\mathrm {wn}(f')=0$ and $\mathrm {wn}(f'')=\mathrm {wn}(f)$. If $f=f_o$ face $f''$ is the new outer face. By Lemma 1, such a vertex $u'$ exists and it is unique.

We proceed with $u\in S$ that are sinks analogously thereby eliminating all the sinks and source in the resulting graph $\overrightarrow{G'}$, where by $G'$ we denote its underlying undirected graph. By Lemma 1, there still exists exactly one inner face $f_o'$ with a non-zero winding number in the resulting graph $G'$.

Lemma 3

$G'$ has exactly one inner face $f_o'$ such that $|\mathrm {wn}(f_o')|=1$.

Since $\gamma (v) = \gamma _f(v) \mod c$ for every face $f\not =f_o,f_o'$ and v incident to f, every edge we added joins a pair of vertices in the same cluster.

Lemma 4

The induced sub-graph $G'[V_i]$ of (undirected) $G'$ does not contain a cycle for $i=0,1,\ldots , c-1$.

Proof

For the sake of contradiction suppose that a cycle C is contained in $G'[V_{j'}]$. Let us choose C such that the area of its interior is minimized. Since $G[V_{j'}]$ is an independent set all the edges of C are newly added. Thus, by looking at the rotation of an arbitrary vertex $v'$ of C we see that $v'$ is incident to a vertex v from $V_j$, $j\not =j'$, in the interior of C. Indeed, no two edges of C subdivide the same face of G.

Using the fact that $\overrightarrow{G'}$ does not contain any source or sink, we show that a vertex w in the interior of C belongs to an oriented cycle $C'$ (by chance also directed in $\overrightarrow{G'}$), whose interior is contained in the interior of C such that $\mathrm {wn}(C')>0$. The cycle $C'$ is obtained by following a directed path in $\overrightarrow{G'}$ (from which it inherits its orientation) passing through v. Either both ends of the path meet each other, they both meet C, or the path meet itself in the interior. In the first two cases we can take $w:=v$ in the last case it can happen that the directed path gives rise to a cycle $C'$ not containing v. However, $C'$ is not induced by a single cluster by the choice of C, and thus, $\mathrm {wn}(C')>0$ by Lemma 1 and $C'$ contains a vertex w from $V_j$. Let $F'$ denote the set of faces in the interior of C and not in the interior of $C'$. In all cases it can be seen by Lemma 1 that $\mathrm {wn}(C')>0$.

Indeed, as we proved in the proof of Lemma 1 $\mathrm {wn}(C') = \mathrm {wn}_j^+(C') + \mathrm {wn}_j^-(C')$. Since $C'$ follows a directed path and is not induced by a single cluster we have $\mathrm {wn}_j^+(W)>0$ and $\mathrm {wn}_j^-(W)=0$. Hence, $\mathrm {wn}(C') = \mathrm {wn}_j^+(C') + \mathrm {wn}_j^-(C')>0$.

By (*) it follows that $C'$ contains the unique inner face with a non-zero winding number in its interior. Then Lemma 3 with (*) yields the following contradiction

$$ 0=\mathrm {wn}(C)=\mathrm {wn}(C')+\sum _{f\in F'} \mathrm {wn}(f)=\mathrm {wn}(C')\not =0 $$

   $\blacksquare$

Let $E'\subseteq \bigcup _i{V_i \atopwithdelims ()2}\setminus E(G')$ such that each edge in $E'$ can be added to the embedding of $G'$ without creating a crossing or increasing the number of inner faces with a non-zero winding number. We do not put any direction on the edges in $E'$. Since every inner face $\not =f_o'$ in $G'$ is simple, and its outer face and the face $f_o'$ are not adjacent to a source or sink, all the edges in $E'$ can be introduced simultaneously without creating a crossing. In particular, no edge of $E'$ subdivides $f_o'$ or the outer face. Let $E''$ denote a maximal subset of $E'$ that does not introduce a cycle in $(G'\cup E'')[V_i]$ for every $i=0,1,\ldots , c-1$ (see Fig. 4), where $G' \cup E'' = (V(G'), E(G') \cup E'')$. By Lemma 4, $E''$ is well-defined.

Fig. 4.

A simple face f of $G'$ (left). The face f subdivided with edges of $E''$ (right). Labels at vertices are their $\gamma$ values (or indices of their clusters).

Lemma 5

$(G'\cup E'')[V_i]$ is a tree for $i=0,1,\ldots , c-1$.

Proof

Suppose for the sake of contradiction that $(G'\cup E'')[V_i]$ for some i is not a tree, and thus, it is just a forest with more than one connected component. It follows that either (1) there exists a cycle in $(G'\cup E'')[V\setminus V_i ]$ containing a vertex v of $V_i$ in its interior or (2) a pair of vertices of $V_i$ in different connected components of $(G'\cup E'')[V_i]$ are incident to the same face of $(G'\cup E'')$. The claim (1) or (2) implies that there exists a cycle C in $(G'\cup E')[V\setminus V_i]$ containing a vertex w of $V_i$ in its interior. Similarly as in the proof of Lemma 4, by following a directed path through v we obtain an oriented cycle $C'$ (this time not necessarily directed) in G, whose interior is contained in the interior of C with $\mathrm {wn}(C')>0$ yielding a contradiction.

Indeed, as we proved in the proof of Lemma 1 $\mathrm {wn}(C') = \mathrm {wn}_i^+(C') + \mathrm {wn}_i^-(C')$. Since $C'$ is not induced by a single cluster and follows in the interior of C a directed path, and C does not have any vertex in $V_i$ we have $\mathrm {wn}_i^+(W)>0$ and $\mathrm {wn}_i^-(W)=0$. Hence, $\mathrm {wn}(C') = \mathrm {wn}_i^+(C') + \mathrm {wn}_i^-(C')>0$.    $\blacksquare$

By Lemma 5, every $F_i$ is a tree. Taking a close neighborhood of each such $F_i$ as a disc representing the cluster $V_i$ we obtain a desired clustered embedding of $(G'\cup E'')$. In the obtained embedding we just delete edges not belonging to G and that concludes the proof of the correctness of our algorithm.

3.2 Normalization

In the present section we normalize the instance so that (i)–(iii) are satisfied. We argued the connectedness in Introduction, and hence, (i) is taken care of. To achieve (ii) is fairly standard by contracting components induced by clusters to vertices. Thus, it remains to satisfy (iii).

We want to sub-divide a non-simple face f into a pair of faces one of which is semi-simple by a monotone path $P'$ w.r.t. $\gamma$. Let uPv denote an oriented monotone sub-walk of f w.r.t. $\gamma$ joining a local minimum u and maximum v of f minimizing $|\mathrm {height}(P)|$. Let $vQv'$ denote the oriented monotone walk with $|\mathrm {height}(P)|=|\mathrm {height}(Q)|$ immediately following P on the facial walk of f, and let $u'Q'u$ be such walk immediately preceding P on the facial walk of f. Note that Q and $Q'$ exists due to the minimality of P and that we have $\mathrm {height}(Q)=\mathrm {height}(Q') = - \mathrm {height}(P)$. Similarly as in [14] we subdivide f into two faces $f'$ and $f''$ by a strictly monotone path $v'P'u'$ w.r.t. $\gamma$. Hence, $\mathrm {height}(P) = \mathrm {height}(P')$. We have $\mathrm {height}(Q)=\mathrm {height}(Q') = - \mathrm {height}(P)= -\mathrm {height}(P')$. Thus, by Lemma 1 if f with $\mathrm {wn}(f)\not =0$ is semi-simple we obtain a simple face $f'$ with $\mathrm {wn}(f')\not =0$ and a semi-simple face $f''$ with $\mathrm {wn}(f'')=0$ as desired. Indeed, $\mathrm {wn}(f'') = \mathrm {height}(P') +\mathrm {height}(Q') + \mathrm {height}(P)+\mathrm {height}(Q)=0$ and $c\cdot \mathrm {wn}(f) = \mathrm {height}(v'P''u') + \mathrm {height}(Q')+\mathrm {height}(P) + \mathrm {height}(Q) =\mathrm {height}(v'P''u') - \mathrm {height}(P')= c\cdot \mathrm {wn}(f')$. It remains to show the following lemma, since both $f'$ and $f''$ are incident to less local minima and maxima than f if f is not semi-simple. Hence, after O(|V|) facial subdivisions we obtain a desired instance, since $|E(I)|=O(|V|)$.

Lemma 6

If the c-graph G is c-planar then by subdividing f of G by $P'$ into a pair of faces $f'$ and $f''$, where $f''$ is semi-simple we obtain a c-planar c-graph. Moreover, $\mathrm {wn}(f')=\mathrm {wn}(f)$ and $\mathrm {wn}(f'')=0$.

Proof

The second statement is proved above. Hence, we deal just with the first one. Let $e_{u}$ and $e_{u}'$ denote the first edge on P and the last edge on $Q'$, respectively. Let $e_{v}$ and $e_v'$ denote the last edge on P and the first edge on Q, respectively. Let $e_{v'}$ and $e_{u'}$ denote the last edge on Q and the first edge on $Q'$. Let $\mathbf{p_{u}=p_{e_{u}}},$ and $\mathbf{p_{v'}=p_{e_{v'}}}$ denote the intersection of the edges $e_u,$ and $e_{v'}$, respectively, with a ray separating a pair of clusters. Let $\omega _u$ and $\omega _v$ denote the wedge between $e_u,e_u'$ and $e_v,e_v'$, respectively, in f.

We presently show that subdividing f with $P'$ preserves c-planarity, since a clustered embedding without $P'$ can be deformed so that $P'$ can be added to a clustered planar embedding without creating a crossing, while keeping the embedding clustered. This is not hard to see if, let’s say $\omega _v$, is convex and the line segment $\mathbf{p_up_{v'}}$ is not crossed by an edge. Since $\omega _v$ is convex, the relative interior of $\mathbf{p_up_{v'}}$ is contained in the interior of f. Note that $u'Q'PQv'$ is a sub-walk of f since f is not simple. We draw a curve C joining $u'$ with $v'$ following the walk $u'Q'PQv'$ in its small neighborhood in the interior f; we cut C at its (two) intersection points with $\mathbf{p_up_{v'}}$ and reconnected the severed ends on both sides by a curve following $\mathbf{p_up_{v'}}$ in its small neighborhood thereby obtaining a closed curve, and a curve $C'$ joining $v'$ and $u'$. Finally, $C'$ can be subdivided by vertices thereby yielding a desired embedding of $G\cup P'$. Otherwise, if $\omega _v$ is concave or $\mathbf{p_up_{v'}}$ is crossed by an edge of G we need to deform the clustered embedding of G so that this is not longer the case.

By a spur with the tip u we understand a closed curve obtained as a concatenation of a line segment contained in a ray separating clusters and a curve contained in the boundary of f passing through exactly one extreme u of f such that the curve is longest possible. The length is the spur is one plus the number of its crossings with rays separating clusters divided by two. If $\omega _u$ is concave, the vertex u is a tip of a spur whose length is the distance of u to a closest other extreme along the face. Note that both P and $Q'$ must be paths in this case. The rough idea in the omitted part of the proof is that shortest spurs have room around them to be deformed while maintaining the embedding clustered such that $P'$ can be added. Spurs are deformed as illustrated in Fig. 5.    $\blacksquare$

Fig. 5.

A pair of deformations of the clustered embedding of G so that f can be subdivided by $P'$. For the sake of clarity clusters are drawn as horiznotal strips rather than wedges.