Extending Simple Drawings

A simple drawing of a graph G (also known as good drawing or as simple topological graph in the literature) is a drawing D(G) of G in the plane such that every pair of edges share at most one point that is either a proper crossing (no tangent edges allowed) or an endpoint. Moreover, no three edges intersect in the same point and edges must neither self-intersect nor contain other vertices than their endpoints. Simple drawings, despite often considered in the study of crossing numbers, have basic aspects that are yet unknown.

The long-standing conjectures on the crossing numbers of \(K_n\) and \(K_{n,m}\), known as the Harary-Hill and Zarankiewicz’s conjectures, respectively, have drawn particular interest in the study of simple drawings of complete and complete bipartite graphs. The intensive study of these conjectures has produced deep results about simple drawings of \(K_n\) [14, 18] and \(K_{n,m}\) [8].

In contrast to our knowledge about \(K_n\), little is known about simple drawings of general graphs. In [16] it was observed that, when studying simple drawings of general graphs, it is natural to try to extend them, by inserting the missing edges between non-adjacent vertices. One of the main results in this paper suggests that there is no hope for efficiently deciding when such operation can be performed.

The complement \(\overline{G}\) of a graph G is the graph with the same vertex set as G and where two distinct vertices are adjacent if and only they are not adjacent in G. Given a simple drawing D(G) of a graph \(G=(V,E)\) and a subset M of candidate edges from \(\overline{G}\), an extension of D(G) with M is a simple drawing \(D'(H)\) of the graph \(H = (V,E\cup M)\) that contains D(G) as a subdrawing. If such an extension exists, then we say that M can be inserted into D(G).

Given a simple drawing, an extension with one given edge is not always possible, as shown by Kynčl [15] (in Fig. 1a the edge uv cannot be inserted, because uv would cross an edge incident either to u or to v). We can extend this example to a simple drawing of \(K_{2,4}\) (Fig. 1b) and we can then use it to construct drawings of \(K_{n,m}\) with larger values of m and n in which an edge uv cannot be inserted. Moreover, Kynčl’s drawing can be extended to a simple drawing of \(K_6\) minus one edge where the missing edge cannot be inserted (Fig. 1c). From this drawing one can construct drawings of \(K_{n}\) with \(n\ge 6\) minus one edge where the only missing edge cannot be inserted.

Extensions, by inserting both vertices and edges, have received a great deal of attention in the last decade, specially for (different classes of) plane drawings [2, 4, 6, 9, 13, 17, 19]. It has also been of interest to study crossing number questions on planar graphs with one additional edge [7, 11, 20]. Note that the term augmentation has also been used in the literature for the similar problem of inserting edges and/or vertices to a graph [10]. Extensions of simple drawings have been previously considered in the context of saturated drawings, that is, drawings where no edge can be inserted [12, 16].

Drawings in which the edge uv cannot be inserted.

Full size image

Our Contribution. We study the computational complexity of extending a simple drawing D(G) of a graph G. In Sect. 2, we show that deciding if D(G) can be extended with a set M of candidate edges is \(\mathsf {NP}\)-complete. Moreover, in Sect. 3, we prove that finding the largest subset of edges from M that extend D(G) is \(\mathsf {APX}\)-hard. Finally, in Sect. 4, we present a polynomial-time algorithm to decide whether an edge uv can be inserted into D(G) when \(\{u,v\}\) is a dominating set for G.

In this section we prove the following result:

Theorem 1

Given a simple drawing D(G) of a graph \(G=(V,E)\) and a set M of edges of the complement of G, it is \(\mathsf {NP}\)-complete to decide if D(G) can be extended with the set M.

Notice first that the problem is in \(\mathsf {NP}\), since it can be described combinatorially. Our proof of Theorem 1 is based on a reduction from monotone \(\mathsf {3SAT}\) [5]. An instance of that problem consists of a Boolean formula \(\phi \) in 3-CNF with a set of variables \(X=\{x_1,\ldots , x_n\}\) and a set of clauses \(K=\{C_1,\ldots , C_m\}\). Moreover, in each clause either all the literals are positive (positive clause) or they are all negative (negative clause). The bipartite graph \(G(\phi )\) associated to \(\phi \) is the graph with vertex set \(X\cup K\) and where a variable \(x_i\) is adjacent to a clause \(C_j\) if and only if \(x_i\in C_j\) or \(\overline{x_i}\in C_j\).

Basic gadgets for the proof of Theorem 1.

Full size image

We now show how to construct a simple drawing from a given formula. We start by introducing our three basic gadgets, the variable gadget, the clause gadget, and the wire gadget, shown in Fig. 2.

The variable gadget contains two nested cycles, avbu on the outside and cvdu on the inside, drawn in the plane without any crossings. Two additional vertices x and y are drawn in the interior of avcu and dvbu, respectively. They are connected with an edge that, starting in x, crosses the edges au, ub, dv, cv, av, and vb, in this order, and ends in y. Another two vertices i and j are drawn inside the region in the interior of avcu that is incident to x. They are connected with an edge that, starting in i, crosses the edges uc, ud, vd, and vc, in this order, and ends in j; see Fig. 2a. Notice that the edge uv can be inserted only in two possible regions: either inside the cycle avcu or inside the cycle dvbu. Drawing the edge uv in any other region would force it to cross uj or xy more than once. The clause gadget and the wire gadget are similarly defined; see Fig. 2b–c.

In each of these three gadgets shown in Fig. 2, the edge uv can only be inserted in the regions where the dashed arcs are drawn. In the rest of the paper, when we refer to the regions in a gadget we mean these regions where the edge uv can be inserted.

In a variable gadget, these regions encode the truth assignment of the corresponding variable \(x_i\): inserting the edge uv in the left region corresponds to the assignment \(x_i=\texttt {true}\), while inserting it in the right region corresponds to \(x_i=\texttt {false}\). We call these left and right regions in a variable gadget the true and false regions, respectively. In a clause gadget, each of the three regions is associated to a literal in the corresponding clause. Wire gadgets propagate the truth assignment of the variables to the clauses. They are drawn between the gadgets corresponding to clauses and variables that are incident in \(G(\phi )\). The idea is that if an assignment makes a literal not satisfy a clause, then the edge uv in the wire gadget blocks the region in the clause gadget corresponding to that literal by forcing uv to cross that region twice.

Let \(w^{(\mathcal {G})}\) denote vertex w in gadget \(\mathcal {G}\). The following lemma shows that we can get the desired behavior with a wire gadget connecting a variable gadget and a clause gadget. The precise placement of a wire gadget with respect to the variable gadget and the clause gadget that it connects is illustrated in Fig. 3.

Reduction from monotone \(\mathsf {3SAT}\). (Color figure online)

Full size image

Lemma 2

We can combine a variable gadget \(\mathcal {X}\), a clause gadget \(\mathcal {C}\), and a wire gadget \(\mathcal {W}\) to produce a simple drawing with the following properties.

• If \(u^{(\mathcal {X})}v^{(\mathcal {X})}\) is inserted in the false region in \(\mathcal {X}\), then inserting \(u^{(\mathcal {W})}v^{(\mathcal {W})}\) prevents \(u^{(\mathcal {C})}v^{(\mathcal {C})}\) from being inserted in one specified target region in \(\mathcal {C}\).

• If \(u^{(\mathcal {X})}v^{(\mathcal {X})}\) is inserted in the true region in \(\mathcal {X}\), then we can insert \(u^{(\mathcal {W})}v^{(\mathcal {W})}\) in a way such that \(u^{(\mathcal {C})}v^{(\mathcal {C})}\) can then be inserted in any region in \(\mathcal {C}\).

Proof

We start with a drawing of the variable gadget \(\mathcal {X}\) and the clause gadget \(\mathcal {C}\) such that the two gadgets are drawn on a line and they are disjoint. A representation of how the wire gadget is then inserted is shown in Fig. 3. In this proof we focus on the wire gadget drawn with blue edges and vertices.

In Fig. 3, gadget \(\mathcal {X}\) lies to the left of gadget \(\mathcal {C}\). The true and false regions in \(\mathcal {X}\) are shaded in green and red, respectively. We assume that the target region in \(\mathcal {C}\) is the leftmost one, shaded in yellow. The left and right regions in the wire gadget are shaded in red and yellow, respectively.

If the edge \(u^{(\mathcal {X})}v^{(\mathcal {X})}\) is inserted in the false region in \(\mathcal {X}\) then the edge \(u^{(\mathcal {W})}v^{(\mathcal {W})}\) cannot be inserted in the yellow region in \(\mathcal {W}\), since it would cross \(u^{(\mathcal {X})}v^{(\mathcal {X})}\) twice. Thus, \(u^{(\mathcal {W})}v^{(\mathcal {W})}\) can only be inserted in the red region in \(\mathcal {W}\). If inserted in that region, \(u^{(\mathcal {C})}v^{(\mathcal {C})}\) cannot be inserted in the yellow region in \(\mathcal {C}\), since it would cross \(u^{(\mathcal {W})}v^{(\mathcal {W})}\) twice. In contrast, if the edge \(u^{(\mathcal {X})}v^{(\mathcal {X})}\) is inserted in the true (green) region in \(\mathcal {X}\), then \(u^{(\mathcal {W})}v^{(\mathcal {W})}\) can be inserted in either of the two regions in \(\mathcal {W}\). In particular, it can be inserted in the yellow region in a way such that \(u^{(\mathcal {C})}v^{(\mathcal {C})}\) can then be inserted in any region in \(\mathcal {C}\).

Finally, notice that if the target region in \(\mathcal {C}\) is not the leftmost one, we can adapt the construction by leaving the region(s) to the left in \(\mathcal {C}\) uncrossed by the wire gadget \(\mathcal {W}\); see the clause gadget in the middle of Fig. 3.    \(\square \)

Let \(\phi \) be an instance of monotone \(\mathsf {3SAT}\)and let \(G(\phi )\) be the bipartite graph associated to \(\phi \). Let \(D(\phi )\) be a 2-page book drawing of \(G(\phi )\) in which (i) all vertices lie on an horizontal line, and from left to right, first the ones corresponding to negative clauses, then to variables, and finally to positive clauses; and (ii) the edges incident to vertices corresponding to positive clauses are drawn as circular arcs above that horizontal line, while the ones incident to vertices corresponding to negative clauses are drawn as circular arcs below it. In an slight abuse of notation, we refer to the vertices in \(D(\phi )\) corresponding to variables and clauses simply as variables and clauses, respectively.

We construct a simple drawing \(D'\) from \(D(\phi )\) by first replacing the variables and clauses by variable gadgets and clause gadgets, respectively, and drawn in disjoint regions. Moreover, the clause gadgets corresponding to negative clauses are rotated \(180^\circ \). We then insert the wire gadgets. The edges in \(D(\phi )\) connecting variables to positive clauses are replaced by wire gadgets drawn as in the proof of Lemma 2; see Fig. 3. Similarly, the edges in \(D(\phi )\) connecting variables to negative clauses are replaced by wire gadgets drawn as the ones before, but rotated \(180^\circ \).

We now describe how to draw the wire gadgets with respect to each other, so that the result is a simple drawing; see Fig. 3 for a detailed illustration. First, we focus on the drawing locally around the variable gadgets. Consider a set of edges in \(D(\phi )\) connecting a variable with some positive clauses. The drawing \(D(\phi )\) defines a clockwise order of these edges around the common vertex starting from the horizontal line. We insert the corresponding wire gadgets locally around the variable gadget following this order. Each new gadget is inserted shifted up and to the right with respect to the previous one (as the blue and green gadgets depicted in Fig. 3). Edges in \(D(\phi )\) connecting a variable with some negative clauses are replaced by wire gadgets in an analogous manner with a \(180^\circ \) rotation. We assign the three different regions in a clause gadget to the target regions in the wire gadgets following the rotation of the edges around the clause in \(D(\phi )\). (Note that we can assume without loss of generality, by possibly duplicating variables, that each clause in \(\phi \) contains three literals.) Thus, locally around a clause gadget, it is then possible to draw the different wire gadgets connecting to it without crossing. Since \(D(\phi )\) is a 2-page book drawing, the constructed drawing \(D'\) is a simple drawing.

Let M be the set of uv edges of all the gadgets. The fact that \(\phi \) is satisfiable if and only if M can be inserted into \(D'\) follows now from Lemma 2, finishing the proof of Theorem 1.

In this section we show that the maximization version of the problem of inserting missing edges from a prescribed set into a simple drawing is \(\mathsf {APX}\)-hard. This implies that, if \({\mathsf {P}}\ne {\mathsf {NP}}\), then no \(\mathsf {PTAS}\) exists for this problem. We start by showing that this maximization problem is \(\mathsf {NP}\)-hard.

Theorem 3

Given a simple drawing D(G) of a graph \(G=(V,E)\) and a set M of edges in the complement \(\overline{G}\), it is \(\mathsf {NP}\)-hard to find a maximum subset of edges \(M'\subseteq M\) that extends D(G).

Our proof of Theorem 3 is based on a reduction from the maximum independent set problem (MIS). By showing that the reduction when the input graph has vertex degree at most three is actually a \(\mathsf {PTAS}\)-reduction we will then conclude that the problem is \(\mathsf {APX}\)-hard.

An independent set of a graph \(G=(V,E)\) is a set of vertices \(S\subseteq V\) such that no two vertices in S are incident with the same edge. The problem of determining the maximum independent set (MIS) of a given graph is \(\mathsf {APX}\)-hard even when the graph has vertex degree at most three [1]. We first describe the construction of a simple drawing \(D'(G')\) from the graph G of a given MIS instance. Then we argue that for a well-selected set of edges M that are not present in \(D'(G')\), finding a maximum subset \(M' \subseteq M\) that can be inserted into \(D'(G')\) is equivalent to finding a maximum independent set of G.

Basic gadgets and drawings for the proof of Theorem 3.

Full size image

3.1 Constructing a Drawing from a Given Graph

We begin by introducing our two basic gadgets, the vertex gadget \(\mathcal {V}\) and the edge gadget \(\mathcal {E}\), shown in Fig. 4. They are reminiscent of the gadgets in the previous section, but adapted to this different reduction. Similarly as in the previous gadgets, there is only one region in which the edge uv can be inserted into \(\mathcal {V}\) and only two regions in which the edge uv can be inserted into \(\mathcal {E}\). These regions are the ones in which the dashed arcs in Fig. 4b are drawn.

In Fig. 4c we combined an edge gadget and two vertex gadgets. This figure shows a copy \(\mathcal {E}^{(e)}\) of the gadget \(\mathcal {E}\) (that corresponds to an edge \(e=wz\)) drawn over two different copies, \(\mathcal {V}^{(w)}\) and \(\mathcal {V}^{(z)}\), of the gadget \(\mathcal {V}\) (that correspond to vertices w and z, respectively). We relabel the vertices in the copies of these gadgets by using the vertex or edge to which they correspond as their superscripts. Since there is only one region in which \(v^{(w)}u^{(w)}\) and \(v^{(z)}u^{(z)}\) can be drawn, inserting both of these edges prevents \(v^{(e)}u^{(e)}\) from being inserted. Inserting either only \(v^{(w)}u^{(w)}\) or only \(v^{(z)}u^{(z)}\) leaves exactly one possible region where \(v^{(e)}u^{(e)}\) can be inserted.

Drawing obtained by a reduction from \(K_4\).

Full size image

We have all the ingredients needed for our construction. Suppose that we are given a simple graph \(G = (V,E)\). This graph admits a 1-page book drawing D(G) in which the vertices are placed on a horizontal line and the edges are drawn as circular arcs in the upper halfplane. Since the edge gadget does not interlink the vertex gadgets symmetrically, we consider the edges in D(G) with an orientation from their left endpoint to their right one.

The following lemma shows that is possible to replace each vertex \(w\in V\) in the drawing by a vertex gadget \(\mathcal {V}^{(w)}\) and each edge \(e\in E\) by an edge gadget \(\mathcal {E}^{(e)}\), and obtain simple drawing \(D'(G')\) (where \(G'\) is the disjoint union of the underlying graphs of the vertex- and edge-gadgets).

Lemma 4

Given a 1-page book drawing D(G) of a graph \(G = (V,E)\), then we can replace every vertex by a vertex gadget and every edge by an edge gadget to obtain a simple drawing.

Proof

We show that the copies \(\{\mathcal {E}^{(e)}\,:\, e\in E\}\) can be inserted into \(\bigcup _{w\in V} \mathcal {V}^{(w)}\) such that such that vertex gadgets corresponding to different vertices are drawn in disjoint regions and for every edge \(e=wz\in E\), \(\mathcal {V}^{(w)}\cup \mathcal {V}^{(z)}\cup \mathcal {E}^{(e)}\) is as in Fig. 4c (up to interchanging the indices w and z), and such that the resulting drawing is simple.

First, for each vertex \(w\in V\) we place the gadget \(\mathcal {V}^{(w)}\) in its position, so all the copies of \(\mathcal {V}\) lie (equidistant) on a horizontal line and do not cross each other. For the edges of G, since the drawing in Fig. 4c is not symmetric, we choose an orientation. We orient all the edges in the 1-page book drawing D(G) of G from left to right. We start by inserting the corresponding \(\mathcal {E}\) gadgets from left to right and from the shortest edges in D(G) to the longest. For an edge wz, the intersections of the gadget \(\mathcal {E}^{(wz)}\): (i) with the edges \(u^{(w)}a^{(w)}\) and \(u^{(w)}b^{(w)}\) are placed to the left of all the previous intersections of other edge gadgets with that edge; (ii) with the edge \(v^{(w)}b^{(w)}\) are placed to the right of all the previous intersections with that edge; (iii) with the edge \(v^{(w)}a^{(w)}\) are placed to the right of previous intersections with gadgets \(\mathcal {E}^{(wt)}\) and to the left of previous intersections with gadgets \(\mathcal {E}^{(tw)}\); (iv) with the edges \(u^{(z)}a^{(z)}\) and \(u^{(z)}b^{(z)}\) are placed to the left of the previous intersections with gadgets \(\mathcal {E}^{(tz)}\); (v) with the edge \(v^{(z)}b^{(z)}\) are placed to the left of all previous intersections; and (vi) with the edge \(v^{(z)}a^{(z)}\) are placed to the left of all previous intersections with gadgets \(\mathcal {E}^{(tz)}\); see Fig. 5.

Moreover, the arcs of an edge gadget connecting two vertex gadgets are drawn either completely in the upper half-plane or completely in the lower one with respect to the horizontal line and two arcs cross at most twice. If they are part of edges in edge gadgets connected to the same vertex gadget, they might cross locally around this vertex gadget. However, after this crossing, they follow the circular-arc routing induced by D(G) (or its mirror image) and do not cross again. Otherwise, with respect to each other, they follow the circular-arc routing induced by D(G) (or its mirror image) and thus cross at most once; see Fig. 5.

Since in neither of the gadgets two incident edges cross, and edges of different gadgets are vertex-disjoint, we only have to worry about edges from different gadgets crossing more than once. By construction, no edge in an edge gadget intersects more than once with an edge in a vertex gadget. Thus, it remains to show that any two edges from two distinct edge gadgets cross at most once. Such two edges are included in a subgraph H of G with exactly four vertices. The drawing induced by the four vertex gadgets and the at most six edge gadgets is homeomorphic to a subdrawing of the drawing in Fig. 5. It is routine to check that it is a simple drawing, and thus any two edges cross at most once.    \(\square \)

3.2 Reduction from Maximum Independent Set

Proof

(of Theorem 3). Given a graph \(G=(V,E)\), we reduce the problem of deciding whether G has an independent set of size k to the problem of deciding whether the simple drawing \(D'(G')\) constructed as in Lemma 4 with a candidate set of edges M (where \(M = \{u^{(w)} v^{(w)}: w\in V\} \cup \{u^{(e)} v^{(e)}: e \in E\}\)) can be extended with a set of edges \(M'\subseteq M\) of cardinality \(|M'|= |E| + k\).

To show the correctness of the (polynomial) reduction, we first show that if G has an independent set I of size k, then we can extend \(D'(G')\) with a set \(M'\) of \(|E| + k\) edges of M. Clearly, the k edges \(\{u^{(w)}v^{(w)} : w \in I\}\) can be inserted into \(D'(G')\) by the construction of the drawing. Since I is an independent set, each edge has at most one endpoint in I. Thus, in every edge gadget \(\mathcal {E}^{(e)}\) at most one of the two possibilities for inserting the edge \(u^{(e)}v^{(e)}\) is blocked by the previous k inserted edges. We therefore can also insert the |E| edges \(\{u^{(e)}v^{(e)}: e \in E\}\).

Conversely, let \(M'\subset M\) be a set of \(|E| + k\) edges can be inserted into \(D'(G')\) and that contains the minimum number of uv edges from vertex gadgets. If the set of vertices \(\{w \in V: u^{(w)}v^{(w)} \in M'\}\) is an independent set of G, then we are done, since at most |E| edges of \(M'\) can be from edge gadgets, so at least k are from vertex gadgets. Otherwise, there are two edges \(u^{(w)}v^{(w)}\) and \(u^{(z)}v^{(z)}\) in \(M'\) such that the corresponding vertices \(w,z\in V\) are connected by the edge \(wz \in E\). By the construction of \(D'(G')\) this implies that the edge \(u^{(wz)}v^{(wz)}\) belongs to M, but it cannot be in \(M'\). By removing the edge \(u^{(w)}v^{(w)}\) and inserting the edge \(u^{(wz)}v^{(wz)}\) into \(D'(G')\), we obtain another valid extension with the same cardinality but one less uv edge from a vertex gadget. This contradicts our assumption.    \(\square \)

The presented reduction can be further analyzed to show that the problem is actually \(\mathsf {APX}\)-hard. Note that the problem we are reducing from, maximum independent set in simple graphs, is \(\mathsf {APX}\)-hard [1] even in graphs with vertex degree at most three. Our reduction can be shown to be an Ł-reduction in that case, implying a \(\mathsf {PTAS}\)-reduction. This shows the following result (details are provided in the full version [3]):

Corollary 5

Given a simple drawing D(G) of a graph G and a set of edges M of the complement of G, finding the size of the largest subset of edges from M extending D(G) is \(\mathsf {APX}\)-hard.

In this section, we consider the problem of extending a simple drawing of a graph by inserting exactly one edge uv for a given pair of non-adjacent vertices u and v. We start by rephrasing our problem as a problem of finding a certain path in the dual of the planarization of the drawing.

Given a simple drawing D(G) of a graph \(G=(V,E)\), the dual graph \(G^*(D)\) has a vertex corresponding to each cell of D(G) (where a cell is a component of \(\mathbb {R}^2\setminus D(G)\)). There is an edge between two vertices if and only if the corresponding cells are separated by the same segment of an edge in D(G). Notice that \(G^*(D)\) can also be defined as the plane dual of the planarization of D(G), where crossings are replaced by vertices so that the resulting drawing is plane.

We define a coloring \(\chi \) of the edges of \(G^*(D)\) by labeling the edges of the original graph G using numbers from 1 to |E|, and assigning to each edge of \(G^*(D)\) the label of the edge that separates the cells corresponding to its incident vertices. Given two vertices \(u,v\in V\), let \(G^{*}(D,\{u,v\})\) be the subgraph of \(G^*(D)\) obtained by removing the edges corresponding to connections between cells separated by an (arc of an) edge incident to u or to v, and let \(\chi '\) be the coloring of the edges coinciding with \(\chi \) in every edge. The problem of extending D(G) with one edge uv is equivalent to the existence of a heterochromatic path in \(G^{*}(D,\{u,v\})\) (i.e., no color is repeated) with respect to \(\chi \), between two vertices that corresponds to a cell incident to u and a cell incident to v, respectively.

We remark that, from this dual perspective, it is clear that the problem of deciding if a simple drawing can be extended with a given set of edges is in \(\mathsf {NP}\).

The general problem of finding an heterochromatic path in an edge-colored graph is \(\mathsf {NP}\)-complete, even when each color is assigned to at most two edges. The proof can be found in the full version [3].

Theorem 6

Given a (multi)graph G with an edge-coloring \(\chi \) and two vertices x and y, it is NP-complete to decide whether there is a heterochromatic path in G from x to y, even when each color is assigned to at most two edges.

However, in our setting the multigraph and the coloring come from a simple drawing. The following theorem shows a particular case in which we can decide in polynomial time if an edge can be inserted.

Theorem 7

Let D(G) be a simple drawing of a graph \(G=(V,E)\) and let u, \(v\in V(G)\) be non-adjacent vertices. If \(\{u,v\}\) is a dominating set for G, that is, every vertex in \(V\setminus \{u,v\}\) is a neighbor of u or v, then the problem of extending D(G) with the edge uv can be decided in polynomial time.

Reduction to the path problem with holes.

Full size image

An algorithm proving this result can be found in the full version [3]. We sketch here the idea. The first step is to reduce our problem to the path problem with holes (PPH): Given two open disks \(h_1, h_2\subseteq \mathbb {R}^2\) whose closures (called holes) are either disjoint or they coincide \(h_1=h_2\), a set \(\mathcal {J}\) of colored Jordan curves in \(\varGamma = \mathbb {R}^2\setminus (h_1\cup h_2)\), and two distinct points p, \(q\in \varGamma \setminus \bigcup \mathcal {J}\), we want to decide if there is a pq-arc intersecting at most one arc in \(\mathcal {J}\) from each color. If \(h_1=h_2\), we say that the instance of the PPH has one hole.

Consider the subdrawing \(D_{u,v}\) of D(G) consisting of u, v, all vertices adjacent to them and all the edges incident to u or to v. Figure 6 illustrates the reduction from the problem of inserting uv in \(D_{u,v}\) to the PPH. Based on our reduction, one can make further assumptions on any instance \((\varGamma , \mathcal {J}, p, q)\) that we consider of the PPH problem: (i) for every two different arcs \(\alpha _1\), \(\alpha _2\in \mathcal {J}\), \(|\alpha _1\cap \alpha _2|\le 1\); (ii) pairs of arcs in \(\mathcal {J}\) with the same color do not cross; and (iii) each arc in \(\mathcal {J}\) has both ends on the union of the boundaries of the holes \(\partial h_1\cup \partial h_2\).

Given an instance \((\varGamma ,\mathcal {J},p,q)\) of the PPH, an arc \(\alpha \in J\) is separating if p and q are on different connected components of \(\varGamma \setminus \alpha \). We divide the arcs in \(\mathcal {J}\) into three different types: (T1) arcs with ends on different holes; (T2) separating arcs with ends on the same hole; and (T3) non-separating arcs with ends on the same hole.

Transforming an instance of PPH: (a) enlarging a hole along an arc and (b) cutting through an arc.

Full size image

Arcs of type T3 can be preprocessed with the operation that we denote enlarging one hole using \(\alpha \), as showed in Fig. 7(a). Once all the arcs in \(\mathcal {J}\) are of type either T1 or T2, the algorithm determines the existence of a feasible pq-arc based on the colors of the arcs in \(\mathcal {J}\). If all the arcs have different colors we have a solution. Otherwise we consider two arcs of the same color. If both arcs are of type T2, then there is no valid pq-arc and our algorithm stops. For handling the cases in which at least one of these arcs is of type T1, the idea is to try to find a solution that does not cross it. To do so, we use the operation denoted cutting through an arc illustrated in Fig. 7(b). If of the two arcs of the same color is of type T1 and the other is of type T2, there is a valid pq-arc if and only if there is a valid pq-arc after cutting through the T1 arc. Otherwise, if both are of type T1, there is a solution if and only if either there is a solution after cutting through the first arc or there is a solution after cutting through the second one. Note that the operation of cutting through an arc produces an instance with only one from an instance with two holes. This guarantees that the algorithm runs in polynomial time.

In this paper we showed that given a simple drawing D(G) of a graph \(G=(V,E)\) and a prescribed set M of edges of the complement of G, it is \(\mathsf {NP}\)-complete to decide whether M can be inserted into D(G). Moreover, it is \(\mathsf {APX}\)-hard to find the maximum subset of edges in M that can be inserted into D(G). We remark that the reduction showing \(\mathsf {APX}\)-hardness cannot replace the one showing \(\mathsf {NP}\)-hardness of inserting the whole set M of edges, since, by construction, in the \(\mathsf {APX}\)-hardness reduction some of the edges in M cannot be inserted.

Focusing on the case \(|M|=1\), we showed that a generalization of this problem is \(\mathsf {NP}\)-complete and we found sufficient conditions guaranteeing a polynomial time decision. We hope that this paves the way to solve the following question.

Problem 1

Given a simple drawing D(G) of a graph G and a pair u, v of non-adjacent edges, what is the computational complexity of deciding whether we can insert uv into D(G) such that the result is a simple drawing?