The Price of Connectivity Augmentation
on Planar Graphs

We start with an asymptotically tight tradeoff between connectivity and local crossing number (regardless of the number of new edges): Every $k$-connected graph is $O(k^2)$-planar (Proposition 2.2). For geometric graphs on $n$ points in convex position, we determine the precise tradeoff (Proposition 2.3). The asymptotically tight bound can be attained even if we augment a given plane triangulation in the topological setting (Theorem 3.2). The geometric setting turns out to be much more constrained: We show that any PSLG can be augmented to a 3-connected 5-planar geometric graph, and this bound is the best possible (Theorem 8.1). However, augmenting a PSLG to a 4-connected geometric graph may already increase the local crossing number to $\mathrm{\Omega }(n)$ (Theorem 8.3).

Table 1 presents an overview of the computational complexity of finding minimum solutions; each field has an entry for the abstract, topological, and geometric setting (in this order); a single entry means that the same result holds in all three settings.

Kant [35] gave an $O(n)$-time algorithm for the 2- and 3-connectivity augmentation of outerplanar graphs with $n$ vertices in the abstract setting, and Gutwenger et al. [27] gave an $O(n(1+\alpha (n))$-time algorithm for the $1\to 2$ augmentation for connected plane graphs. For a PSLG tree on $n$ vertices, there is an $O(n^4)$-time algorithm for 2-connectivity augmentation [4]. (Biconnectivity augmentation can also be solved optimally over outerplanar graphs, where both $G$ and $G^{\prime }$ must be outerplanar [26].) We give an $O(n)$-time algorithm for the minimum augmentation of a plane tree to a 3-connected plane graph in the topological settings (Theorem 4.2). In the geometric setting, 3-connectivity augmentation of trees remains open.

For a straight-line triangulation on $n$ points in convex position, we give a combinatorial characterization of 3- and 4-connected augmentations. In this setting, the dual graph is a tree. We use the dual tree for a dynamic programming algorithm to compute a minimum augmentation to a $k$-connected $\mathrm{\ell }$-planar geometric graph for $k\in \{3,4\}$ and constant $\mathrm{\ell }\in \mathbb{N}$ in $O(n)$ time (Theorem 7.2).

In most settings, however, the $c\to k$ connectivity augmentation problem is NP-complete. We prove the following theorem using several reductions from planar 3-SAT.

Our reductions presented in Section 5 (from planar 3-SAT) work similar to [4] in the sense that the truth assignment of a variable is encoded in one of two possible perfect matchings on a subset of vertices whose degree must be augmented. The proof in [4] is specific to the geometric setting, and it is not trivial to generalize it to the other two settings. Moreover, $c$-connected gadgets for $c\in \{2,3,4\}$ required delicate new designs to ensure that the desired behavior in the reduction [4] go through, especially when $G$ is a triangulation.

In a $k$-connected graph $G$ on $n>k$ vertices, the minimum vertex degree $\delta (G)$ is at least $k$. All new hardness reductions in Table 1 hinge on increasing the degree of a set of special vertices from $c$ to $k$, using the minimum number of new edges, while maintaining planarity. As a consequence, we also prove that the following min-degree augmentation problems are NP-complete:

A flip (a.k.a. edge exchange) in a combinatorial triangulation (i.e., edge-maximal planar graph) is an elementary operation that removes one edge and inserts a new edge, producing another triangulation. The flip diameter on $n$ vertices is the minimum number of flips that can transform any combinatorial triangulation into any other. Current bounds on the flip diameter use a canonical form, which is a triangulation with a Hamiltonian cycle. Since 4-connected triangulations are Hamiltonian [52] (see also [38, 44, 49] for extensions to beyond-planar graphs), the flip distance to a Hamiltonian or a 4-connected triangulation was studied [14, 16]. Bose et al. [13] posed the following problems: Given a combinatorial triangulation $T$, find the minimum number of flips that can take it to a 4-connected (resp., Hamiltonian) triangulation. Our hardness reduction for the $3\to 4$ connectivity augmentation problem can be modified to show that finding the flip distance to 4-connectedness is also NP-complete (Corollary 1.3).

A simultaneous flip in a combinatorial triangulation is an operation that performs one or more edge flips simultaneously (each of which is a valid flip, and they can be performed independently) [24]. Bose et al. [12] showed that every triangulation on $n\ge 6$ vertices can be transformed into a 4-connected triangulation with a single simultaneous flip; the number of flipped edges is at most $\lfloor (2n-7)/3\rfloor$ [16]. We show that it is NP-complete to find a minimum simultaneous flip to 4-connectivity (Corollary 1.3). By inserting all simultaneously flipped edges (without removing any edges), we obtain a 4-connected 1-planar graph. In fact, finding a minimum augmentation to a 4-connected 1-planar graph in a triangulation is equivalent to finding a minimum simultaneous flip to 4-connectivity [12, Section 3].

In Section 6, we give an EPTAS for the first of the two problems (Theorem 6.1). We also give some intuition for why our techniques do not directly apply to the second problem.

While we aim for increasing the vertex-connectivity of a given graph, analogous problems can be considered for edge-connectivity [5, 17, 33, 43, 50, 54]. Some of our techniques might extend to edge-connectivity, however, such adaptations are not immediate and are beyond the scope of this paper.

We have measured the distance to planarity by the local crossing number. However, there are many other notions of beyond-planarity. For example, García et al. [25] studied the connectivity augmentation problem for geometric biplane graphs, which admit a straight-line drawing in the plane and a 2-coloring of the edges such that no two edges of the same color cross (a.k.a. graphs with geometric thickness 2). They showed that every sufficiently large point set in the plane in general position admits a 5-connected geometric biplane graph, and the connectivity bound 5 cannot be improved. Furthermore, every PSLG (other than a wheel or a fan) can be augmented into a 4-connected geometric biplane graph, and the connectivity bound 4 cannot be improved.

Let $G=(V,E)$ be a $k$-connected $\mathrm{\ell }$-planar graph on $n=|V|$ vertices. Then $\mathrm{deg}(v)\ge k$ for every $v\in V$, and so $|E|\ge kn/2$. Assume w.l.o.g. that $k\ge 8$, hence $|E|\ge 4n$. By the Crossing Lemma [3, 15, 40], the total number of crossings in any drawing of $G$ is $\mathrm{cr}(G)=\mathrm{\Omega }({|E|}^3/n^2)=\mathrm{\Omega }(k^{3}n)$. By the pigeonhole principle, there is an edge with $\mathrm{\Omega }(\mathrm{cr}(G)/|E|)=\mathrm{\Omega }({|E|}^2/n^2)=\mathrm{\Omega }(k^2)$ crossings; hence $\mathrm{\ell }=\mathrm{\Omega }(k^2)$ and $k=O(\sqrt{\mathrm{\ell }})$.

For a matching lower bound, let $V$ be the set of $n\ge k+1$ points in the plane in general position. Assume w.l.o.g. that they have distinct $x$-coordinates. Sort the points by $x$-coordinate and connect every point to its $k$ neighbors on the left and right. The first $k+1$ points induce a complete graph, which is $k$-connected. By induction, the first $i$ points also induce a $k$-connected graph for . Any edge can only cross other edges with overlapping $x$-projections, so every edge has $O(k^2)$ crossings. $◀$ Determining the precise dependency between $k$ and $\mathrm{\ell }$ remains largely open. One exception is the case $k=1$: The maximum connectivity of a 1-planar graph is 7. Every 1-planar graph on $n\ge 3$ vertices has at most $4n-8$ edges [45], so the minimum degree is at most $7$, hence its connectivity is at most 7. This degree bound is tight: Biedl [9] constructed 1-planar graphs with minimum degree 7, which happen to be 7-connected. However, the connectivity of optimal 1-planar graphs (which have precisely $4n-8$ edges) is either 4 or 6 [23, 48]; there are edge-maximal 1-planar graphs with $\frac{8}{3}n-O(1)$ edges, where the connectivity is only 2 [30].

We can determine the exact tradeoff between connectivity and local crossing number for geometric graphs when the vertices are in convex position. For integers $k,n\in \mathbb{N}$, , the $k$-circulant graph $G=(V,E)$ is defined on the vertex set $V=\{v_0,\mathrm{\dots },v_{n-1}\}$, where $v_i{v}_j\in E$ if and only if the cyclic distance between $i$ and $j$ is at most $k$, that is, $\min \{|i-j|,n-|i-j|\}\le k$; see Figure 2.

Let $k\in \mathbb{N}$, and let $G=(V,E)$ be the $k$-circulant graph on $n$ vertices, that is, the vertices are on a circle, and each vertex is adjacent to $k$ neighbors in both cw and ccw direction along the circle. Elementary counting shows that every edge crosses at most $k^2-k$ other edges. We show that $G$ is $2k$-connected. We need to show that $G-D$ is connected for any $D\subset V$ with $|D|=2k-1$. Let $s,t\in V\setminus D$. Then $s$ and $t$ decompose the circle into two arcs. One of them contains at most $k-1$ vertices in $D$. We construct an $st$-path ${\pi }_{st}$ by following this arc, and skip all vertices in $D$. Since we skip at most $k-1$ consecutive vertices, all edges of ${\pi }_{st}$ are present in $G-D$, and so $G-D$ is connected.

Now let $G=(V,E)$ be a geometric graph on $n\ge 2k$ points in convex position, with minimum degree at least $2k$. We define the length of an edge $uv$ as the minimum number of edges in a path on the boundary of the convex hull. Then $|E|\ge kn$, and elementary counting shows that $G$ has at least one edge of length at least $k$. Let $e$ be a shortest edge among all edges of length at least $k$. We claim that if $e$ has length $\mathrm{\ell }\ge k$, then it has at least $k^2-3k+2\mathrm{\ell }\ge 2k^2-k$ crossings. Assume w.l.o.g. that $V=\{v_0,\mathrm{\dots }{v}_{n-1})$ in cyclic order along the convex hull of $V$, and $e=(0,\mathrm{\ell })$. Every edge that crosses $e$ has on endpoint in $\{v_1,\mathrm{\dots },v_{\mathrm{\ell }-1}\}$ and one in $\{v_{\mathrm{\ell }+1},\mathrm{\dots },v_{n-1}\}$. Then ${\sum }_{i=1}^{\mathrm{\ell }-1}\mathrm{deg}(v_i)\ge 2k(\mathrm{\ell }-1)$. We subtract the number of vertex-edge pairs $(i,e^{\prime })$ such that $1\le i\le \mathrm{\ell }-1\}$ and $e^{\prime }$ does not cross $e$. Every such edge $e^{\prime }$ has length less than $k$. By symmetry, it is enough to count pairs $(i,e^{\prime })$ where $e^{\prime }$ is a “left” edge, that is, $e^{\prime }=\{i,j\}$ and . The number of such edges for $i=1,2,\mathrm{\dots },\mathrm{\ell }-1$ is $1,2,3,\mathrm{\dots },k-1,k-1,\mathrm{\dots },k-1$, which sums to $\left(\genfrac{}{}{0pt}{}{k}{2}\right)+(\mathrm{\ell }-k)(k-1)$. So edge $e$ crosses at least $2k(\mathrm{\ell }-1)-2\left(\left(\genfrac{}{}{0pt}{}{k}{2}\right)+(\mathrm{\ell }-k)(k-1)\right)=k^2-3k+2\mathrm{\ell }\ge k^2-k$ edges. This is a lower bound for the local crossing number of $G$. $◀$

Let $G=(V,E)$ be a plane graph on $n\ge 6$ vertices. We may assume that $G$ is an edge-maximal plane graph (i.e., a triangulation). Cardinal et al. [16, Theorem 3] proved that $G$ can be transformed into a 4-connected edge-maximal planar graph $G^{\prime }=(V,E^{\prime })$ using a simultaneous flip of at most $\lfloor (2n-7)/3\rfloor$ edges. Now $G=(V,E\cup E^{\prime })$ is 4-connected (since it contains $G^{\prime }$) and 1-planar (an edge has a crossing iff it participates in a flip). $◀$

For plane graph augmentation, we prove a tight tradeoff (matching Proposition 2.2).

Without loss of generality assume we are given a plane triangulation $G=(V,E)$ and a $k\in \mathbb{N}$. The dual graph $𝒟$ of $G$ is a planar graph of maximum degree 3. We can partition $𝒟$ into a collection $𝒞=\{C_1,\mathrm{\dots },C_t\}$ of connected subgraphs, each containing at least $2k-1$ and at most $6k-2$ nodes as follows. Consider an arbitrary spanning tree $𝒯$ of $𝒟$, and recursively partition $𝒯$ into subtrees by deleting an edge incident to a centroid node, until any further partition would produce a subtree with less of than $2k-1$ nodes (see Figure 3).

For every $i=1\mathrm{\dots },t$, let $R_i$ denote the region formed by the union of triangles in $C_i$; and let $V_i\subset V$ denote the set of all vertices of the triangles in $C_i$. By Euler’s formula, applied for the triangles in $C_i$, we have $k\le |V(C_i)|\le 6k$. We call the vertex sets $V_1,\mathrm{\dots },V_t$ clusters, We also define a cluster graph $𝒢$, where the nodes correspond to the $t$ clusters, and nodes $V_1$ and $V_j$ are adjacent in $𝒢$ if $C_i$ and $C_j$ contain two triangles that share an edge. Note that a vertex $v\in V$ may be part of arbitrarily many clusters (e.g., if $v$ is a high-degree vertex), yet each cluster is adjacent to $O(k)$ other clusters in $𝒢$.

We can augment $G$ as follows. (1) Augment each cluster $V_i$ to a clique, drawing all new edges along shortest paths in the region $R_i$. (2) For each pair of adjacent clusters, $V_i$ and $V_j$, add a matching of size $k-|V_i\cap V_j|$ between $V_i\setminus V_j$ and $V_j\setminus V_i$, drawing the new edges along shortest paths in the region $R_i\cup R_j$. Let $G^{\prime }$ denote the augmented graph.

First, we show that $G^{\prime }$ is $k$-connected. Specifically, we show by induction on $i\ge 1$ that if $i$ clusters induce a connected subgraph of the cluster graph, then the union of the clusters induce a $k$-connected graph in $G^{\prime }$. The claim is clear in the base case $i=1$. For the induction step, we use Menger’s Theorem. Assume that the claim holds for $i-1$ clusters. The union of $i$ clusters is composed of two parts, $A$ and $B$, where $A$ is the union of $i-1$ clusters, including cluster $V_j$, and $B=V_i$ is the $i$-th clusters. Both $G^{\prime }[A]$ and $G^{\prime }[B]$ are $k$-connected by the induction hypothesis, they share $|V_i\cap V_j|\ge 2$ vertices, and are connected by a matching of size $k-|V_i\cap V_j|$ (which is disjoint from the shared vertices). Let $a_1=b_1,\mathrm{\dots },a_s=b_s$ be the shared vertices, and let $a_t{b}_t$, $t=s+1,\mathrm{\dots }k$, be the matching with $a_i\in A\setminus B$ and $b_i\in B\setminus A$. Let $a\in A$ and $b\in B$ be arbitrary vertices. By Menger’s Theorem, there are $k$ internally disjoint paths from $a$ to $a_1,\mathrm{\dots },a_k$ in $G^{\prime }[A]$, hance $k$ internally disjoint path from $a$ to $b_1,\mathrm{\dots },b_k$ in $G^{\prime }[A\cup B]$. Since $G^{\prime }[B]$ is a clique, we obtain $k$ internally disjoint paths between $a$ and $b$ in $G^{\prime }[A\cup B]$. By Menger’s Theorem, $G^{\prime }[A\cup B]$ is $k$-connected.

Second, we claim that $G^{\prime }$ is $O(k^2)$-planar. Consider an edge $e$ in a cluster $C$. In the complete graph of $C$, edge $e$ is crossed by $O(k^2)$ other edges. Cluster $C$ is adjacent to $O(k)$ other clusters, each of which is connected to $C$ by a matching of size $O(k)$. Edge $e$ crosses $O(k^2)$ edges in these matchings. Therefore, any edge in a cluster crosses $O(k^2)$ other edges in $G^{\prime }$. Now consider an edge $f$ of a matching between two adjacent clusters $A$ and $B$. Then $f$ can cross any of the $2\cdot O(k^2)$ edges in the two cliques induced by clusters $A$ and $B$. It can also cross the $2\cdot O(k^2)$ edges in the $O(k)$ matchings between $A$ (resp., $B$) and their adjacent clusters. Overall, any edge in $G^{\prime }$ has $O(k^2)$ crossings. $◀$

We present our construction of $G$ as an inductive proof on $n$, which can be easily turned into a linear-time recursive algorithm. For simplicity, we call the edges of $E(G)\setminus E(T)$ the new edges and illustrate them in red. For the induction base of $n=4$, we set $G=K_4$. So let us henceforth assume that $n\ge 5$. We use a stronger induction hypothesis, where we require that $n_2(T)$ is even; we later show how to handle the odd case. This assumption ensures that each leaf of $T$ is incident to exactly two new edges, each vertex of degree $2$ to exactly one new edge, and all other vertices to no new edges. We distinguish four cases.

Case 1:

A vertex $v$ has two consecutive neighbors $a,b$ of $\mathrm{deg}(a)=\mathrm{deg}(b)=1$.

Say $a$ comes clockwise after $b$ at $v$. We remove $a$ and $b$ from $T$. If $v$ is not a leaf after this removal, then we add another leaf $w$ at $v$; otherwise $v$ takes the role of $w$. We denote the new tree by $T^{\prime }$ and note that $n_2(T^{\prime })=n_2(T)$, i.e., the number of degree-$2$ vertices remains the same. In order to apply the induction, we must also ensure that $T^{\prime }$ has at least $4$ vertices if no new leaf was added, i.e., $T$ has at least $6$ vertices. This is the case as otherwise $T$ corresponds the tree $T_5^{\ast }$ depicted in Figure 5, for which $n_2(T_5^{\ast })$ is odd. In the obtained solution $G^{\prime }$ with $T^{\prime }\subseteq G^{\prime }$, vertex $w$ is incident to two edges in $F^{\prime }=E(G^{\prime })-E(T^{\prime })$, say $wx$ comes clockwise after $wy$ at $w$. Then we remove $wy$ and insert $ab$ and $by$.

We define a leg as a vertex $v$ in $T$ of $\mathrm{deg}(v)=2$ with neighbor $a$ of $\mathrm{deg}(a)=1$.

Case 2:

A vertex $v$ has two neighbors $a,b$ that are legs which are either consecutive or have a leaf $c$ between them.

We may assume that $a$ comes clockwise after $b$, and if it exists, $c$ comes after $b$ and before $a$ at $v$. Then we remove $a,b$, their adjacent leaves $a^{\prime },b^{\prime }$ and $c$. If $v$ is not a leaf after this removal, then we add another leaf $w$ at $v$; this ensures that $v$ does not have degree $2$. As before, we aim to recurse on the resulting tree $T^{\prime }$. Note that $n_2(T^{\prime })=n_2(T)-2$ because $a$ and $b$ are removed and $v$ has degree $1$ or at least $3$ in $T^{\prime }$. We also ensure that $T^{\prime }$ has at least $4$ vertices. In the case that we introduce a new leaf $w$, this is due to the fact that $v$ has at least two more neighbors. In the other case, we must exclude the case that $T^{\prime }$ is a path on three vertices. However, this would imply that $T$ is either the tree $T_7^{\ast }$ or $T_8^{\ast }$, illustrated in Figure 5, both of which have an odd number of degree-$2$ vertices. Thus, we may apply induction on $T^{\prime }$.

In the obtained solution $G^{\prime }$, vertex $w$ has two incident edges in $F^{\prime }=E(G^{\prime })-E(T^{\prime })$, say $wx$ comes clockwise after $wy$ at $v$. Then we remove $wx,wy$ and insert $a^{\prime }x$, $a^{\prime }{b}^{\prime }$, and $b^{\prime }y$. If $c$ exists in $T$, we insert $ac$ and $cb$, otherwise we insert only $ab$.

Case 3:

A vertex $v$ with $\mathrm{deg}(v)=2$ has a neighbor $b$ that is a leg adjacent to leaf $a$.

In this case we delete $a$ and $b$ and recurse on $T^{\prime }=T-\{a,b\}$; note that $n_2(T^{\prime })=n_2(T)-2$. Moreover, if $T^{\prime }$ had only $3$ vertices, then $T$ would correspond to a path on $5$ vertices for which $n_2(T)$ would be odd. Hence, we may apply the induction. In the obtained solution $G^{\prime }$, vertex $v$ has two incident edges in $F^{\prime }=E(G^{\prime })-E(T^{\prime })$, say $vx$ and $vy$. Then we remove $vx,vy$ and insert $va$, $ax$, and $by$.

Case 4:

A vertex $v$ (with $\mathrm{deg}(v)=3$ or $4$) has a neighbor $p$ with $\mathrm{deg}(p)\ge 3$, one neighbor $a$ which is a leg and otherwise only leaves.

By Case 1, we may assume that no two leaves are consecutive. Hence, either $v$ has exactly one leaf $b$ or two leaves $b,c$ which are separated by $p$ and $a$, see also Figure 6. In this case we delete $a,b,c$ and the leaf $a^{\prime }$ of $a$, and insert a new leaf $w$ at $v$. We recurse on the resulting tree $T^{\prime }$. Note that $n_2(T^{\prime })=n_2(T)$ as we deleted $a$ and $v$ has degree $2$ in $T^{\prime }$. Moreover, due to the fact that $p$ has $\mathrm{deg}(p)=3$, $T^{\prime }$ has at least $4$ vertices. In the solution $G^{\prime }$ obtained by induction, vertex $v$ is incident to one edge, say $vz$, and vertex $w$ to two edges, say $wx$ and $wy$, in $F^{\prime }=E(G^{\prime })-E(T^{\prime })$. Then we remove $wx,wy,wz$ and insert $a^{\prime }y$, $ab$, and $bz$. If $c$ does not exist, we insert $a^{\prime }x$ and otherwise $a^{\prime }c,cx$.

This completes the construction of $G$ with $T\subseteq G$. To show that the case distinction is exhaustive, root the tree $T$ at an arbitrary vertex and consider a lowest vertex $v$ that is neither a leaf nor a leg. All but one neighbor $p$ of $v$, are either leaves or legs. If $v$ has $\mathrm{deg}(v)=2$, then Case 3 applies. Otherwise, apart from $p$, $v$ has two consecutive leaves (Case 1), two legs which are consecutive or have a leaf between them (Case 2), or one leg and otherwise only leaves (Case 4).

It remains to argue that the resulting graph $G$ is $3$-connected. This is clear in the base case $G=K_4$. In each remaining case, it suffices to observe that $G$ is obtained from a $3$-connected graph $G^{\prime }$ by a local modification that is a sequence of so-called BG-operations; these operations were introduced by Barnette and Grünbaum [8] and preserve $3$-connectivity. In a $(1,2)$-operation we subdivide an edge $xy$ by a new vertex $w$ and insert an edge $vw$ with $v\ne x,y$. In a $(2,3)$-operation we subdivide edge $xy$ by vertex $a$ and edge $vw$ by vertex $b$ and insert the edge $ab$. Figures 4 and 6 illustrate how up to three of these operations suffice.

Lastly, we show how to handle the case that $n_2(T)$ is odd. We choose an arbitrary vertex $v$ of degree $2$ and contract one of its incident edges to obtain a tree $T^{\prime }$. Using our above machinery, we obtain a $3$-connected graph $G^{\prime }$ with $|E(G^{\prime })|-|E(T^{\prime })|=\lceil \frac{2n_1(T)+n_2(T)-1}{2}\rceil =\lceil \frac{2n_1(T)+n_2(T)}{2}\rceil -1$. Now we reintroduce $v$ by a $(1,2)$-operation on its edge, connecting $v$ to an arbitrary non-neighbor in an incident face. As this preserves $3$-connectivity, this completes the proof. $◀$

If $F$ is a sequence of edge flips making $G$ $4$-connected, then every separating triangle in $G$ must be incident to at least one edge in $E^{\prime }$ (otherwise the missing separating triangle remains in $G$ after all flips have been performed, and the graph is not $4$-connected). Thus, $F$ has length at least $\tau$.

Now consider the edges of $E^{\prime }$ in some arbitrary order $e_1,e_2,\mathrm{\dots },e_{|E^{\prime }|}$. Define a sequence of edge flips as follows. Let $1\le i\le |E^{\prime }|$, and assume the first $i-1$ edges of $E^{\prime }$ have already been processed. Then for the $e_i$, do the following:

• $\mathrm{■}$

  if $e_i$ is not present in $G$ (because it has already been flipped previously) or does not bound any separating triangles in $G$, don’t flip any edge;

• $\mathrm{■}$

  otherwise, if $e_i$ is incident to multiple separating triangles in $G$, flip $e_i$;

• $\mathrm{■}$

  otherwise, if none of the $3$ edges of the unique separating triangle $T$ incident to $e$ are incident to any other separating triangle, flip $e_i$;

• $\mathrm{■}$

  otherwise, flip an edge of $T$ incident to at least $2$ separating triangles.

By the definition of this sequence and of $E$, it is clear that for any separating triangle in $G$, at least one of its $3$ edges gets flipped. Moreover, every edge that is flipped obeys the conditions of Lemma 6.2 (at the time it is flipped), and thus, no new separating triangle is introduced and the resulting graph is $4$-connected.

Let us describe how to carry out the procedure in linear time. For each edge, we will maintain a set of pointers to the separating triangles it bounds in a doubly-linked list. Each separating triangle also has corresponding back-pointers, so that from a separating triangle we can access the three pointers pointing to it in constant time. We can initialize this structure by computing the set of separating triangles incident to each edge in $O(n)$ total time (this can be done for example by computing a $4$-block decomposition of the triangulation in linear time [36]).

For a given edge, we can then test in constant time if it bounds $0$, $1$ or at least two separating triangles. In the case it bounds exactly one separating triangle $T$, we can test in constant time whether this is also the case for the two other edges bounding $T$. Each time we flip an edge $e$, we go through the set of separating triangles it used to bound by traversing its associated doubly-linked list and following the pointers it stores. For each such separating triangle, we delete it from the doubly-linked lists of the three edges which (used to) bound it by following the back-pointers. This costs constant time per deleted separating triangle.

Because no new separating triangle is created at any point, every separating triangle is deleted once and the triangulation starts out with $O(n)$ separating triangles, the total runtime is $O(n)$. $◀$

It is tempting to try to carry out the reduction by simply flipping the edges of $E^{\prime }$ in some arbitrary order (or perhaps skipping an edge if it is no longer incident to any separating triangle by the time it is considered). However, this strategy may fail as illustrated in Figure 11. Thus, a more careful strategy is needed. Our algorithm flips only edges that bound separating triangles and do not create any separating triangle, thus strictly decreasing the number of separating triangles with each flip.

Recall that a tree decomposition of $G$ is a mapping of $G$ into a tree $T_G$ whose vertices we shall call bags. A bag $B$ is associated with a subset of vertices $V_B$. Every vertex appears in at least one bag and induces a single subtree in $T_G$, and if two vertices are adjacent in $G$ then there is a bag in $T_G$ containing both vertices. The width of $T_G$ is the size of its largest bag. We root $T_G$ arbitrarily. We can build a tree decomposition of $G$ of width $O(k)$ in $n\cdot 2^{O(k)}$ time with the following properties [11, 39]:

• $\mathrm{■}$

  the number of bags is $O(n)$;

• $\mathrm{■}$

  the maximum degree of a bag is 3;

• $\mathrm{■}$

  for a bag with two children, all three bags have identical subsets of vertices; and

• $\mathrm{■}$

  for a bag with a single child the two subsets differ by one.

Since $G$ is planar, each bag defines an induced subgraph with $O(k)$ edges. Note that, by definition, if $G$ has a clique, these vertices must appear in a bag of $T_G$. Thus, every 3-cycle in $C$ must appear in at least one bag of $T_G$. We compute $E^{\prime }$ using dynamic programming as follows. We say that a subset $S$ of edges satisfies a subtree of $T_G$ if every 3-cycle of $C$ that appears in a bag of the subtree contains at least one edge in $S$. For each bag $B$ and for each subset $S$ of the $O(k)$ edges in $V_B$, we define a subproblem $A_{B,S}$ of computing the minimum cardinality set $S^{\prime }$ of edges satisfying the subtree rooted at $B$ subject to choosing the edges in $S$ in the induced subgraph of $V_B$. Thus there are $n\cdot 2^{O(k)}$ total subproblems. By our degree-3 assumption, the children of parents of high-degree simply receive the information from their parent without making any choices. The child of a low degree bag has to make choices about the incident edges to the potential new vertex $v$. The degree of $v$ in the induced subgraph is $O(k)$ which implies that we have to make $2^{O(k)}$ binary choices. Some of these choices are fixed: if the addition of $v$ closes a 3-cycle in $C$, the cycle has two incident edges to $v$ and the choices are valid only if at least one edge of the separating triangle is chosen. Therefore to compute each subproblem there is $k\cdot 2^{O(k)}=2^{O(k)}$ nonrecursive work. Since the tree decomposition has $O(n)$ nodes, this approach leads to a $n\cdot 2^{O(k)}$ runtime. $◀$

We can now give the proof of Theorem 6.1.

The idea is to apply Baker’s layer shifting technique [7] to the hitting set formulation of the problem. We actually solve the more general problem of hitting an arbitrary subset $C$ of $3$-cycles of $G$, given as an input.

Assume without loss of generality that $ϵ\le 1/2$ and set $k=\lceil 1/\epsilon \rceil$. Choose an arbitrary vertex $v_0$ of $G$ and label all vertices of $G$ according to their (shortest path) distance to $v_0$. We call the set of vertices at a specific distance from $v_0$ a layer of $G$. For , assign the color $i$ to all edges incident to two vertices labeled $(i\text{ mod }k)$ (edges joining two vertices in consecutive layers do not get assigned a color).

Let $E^{\ast }$ be a smallest subset of edges such that every $3$-cycle in $C$ is incident to at least one edge in $E^{\ast }$. Notice that there is at least one of the $k$ colors, say, $c$, for which at most $|E^{\ast }|/k$ edges from $E^{\ast }$ get assigned the color $c$.

Now imagine decomposing $G$ into the subgraphs $G_0,\mathrm{\dots }{G}_p$ each induced by $k+1$ consecutive layers, starting at a layer whose label is $(c\text{ mod }k)$ (except eventually for the first subgraph which starts at layer $0$, and the last subgraph which might consist of fewer than $k+1$ consecutive levels). Note that consecutive subgraphs overlap at layers $(c\text{ mod }k)$. Every $3$-cycle in $C$ appears in one of the subgraphs, as it necessarily has its $3$ vertices in at most $2$ consecutive layers, and every pair of consecutive layers appears in one of the subgraphs. Taking the union of optimal solutions for the problem on each subgraph (with $C$ restricted to the $3$-cycles which appear in that subgraph) thus gives a valid solution for $G$. Let $E_1,\mathrm{\dots },E_p$ be such optimal solutions, and for $1\le j\le p$ let $E^{\ast }[G_j]$ denote the subset of edges in $E^{\ast }$ which appear in $G_j$. We have that

where the second inequality stems from the fact that $E^{\ast }[G_j]$ is a valid solution for $G_j$, the third from the fact that only the edges of color $c$ get counted twice (and there are at most $|E^{\ast }|/k$ such edges) and the last from the choice of $k=\lceil 1/ϵ\rceil$.

The graphs $G_0,\mathrm{\dots },G_p$ are all $(k+1)$-outerplanar and thus have treewidth $O(k)$ [10]. Using Lemma 6.4, we can thus solve the problem optimally for each $G_j$ in $|V(G_j)|2^{O(1/ϵ)}$ time. The total runtime is then ${\sum }_{1\le j\le p}|V(G_j)|2^{O(1/ϵ)}=n\cdot 2^{O(1/ϵ)}$. We can carry out the described procedure for each value of $1\le c\le k$ (note that we don’t know the right value of $c$ to choose a priori) and take the best solution. This adds a factor of $1/ϵ$ that gets absorbed by the exponential. The previous discussion, together with Lemma 6.3, then gives the sought result. $◀$

While Baker’s method of decomposing a planar graph into overlapping layers of small treewidth and combining the solutions is classical, it is interesting to note that a direct adaptation fails for the problem of approximating a smallest set of edges which make a triangulation $4$-connected when flipped simultaneously (or the equivalent problem of augmenting a triangulation to $1$-planar $4$-connected via edge insertions). This is because, while this problem is still efficiently solvable for small treewidth, taking the union of solutions might lead to selecting edges which are not simultaneously flippable. Perhaps this could be overcome by combining the solutions more carefully, but we leave the problem of finding a PTAS for the simultaneous case open here.

Accornero, Ancona and Varini [2] present an algorithm and claim it computes the minimum number of edges hitting all separating triangles in a given triangulation. Note that this result together with our reduction in Section 5 (Corollary 1.3) would imply P=NP. Although their algorithm computes a set of edges that hits all separating cycles, we claim this set is not minimum. We attempt here to give a short intuition for that. In short, their algorithm computes (the equivalent of) a 4-block tree of the input triangulation $T$, a decomposition of $T$ into maximal 4-connected components (4-blocks) hierarchically organized as the nesting structure of separating triangles that bound the maximal components. At each level, the edges are weighted with the cost of the optimal solution for the children nodes that contain said edge in their outer face. Note that every edge bounds at most two separating triangles in the next level of the tree and, therefore, there are at most two children associated with the same edge. At the root of the tree (and recursively in every node) they then compute the minimum weight subset of edges that hit every separating triangle in the maximal 4-block associated with the node. In [2, Theorem 3] there is an implicit assumption that the optimal solution contains a single edge of each separating triangle, since the weights are computed based on the cost of recursive solutions that flip a specific edge. That is not true, for example, in our reduction where the optimal solution may flip two edges of a separating triangle bounding the literal gadget (blue edges in Figure 8).

If $G^{\prime }$ is 3-connected, then the two endpoints of a diagonal $e\in E$ cannot be a 2-cut, and so some edge $f\in F$ connects the two components of $G-ab$. Since the vertices are in convex position, then $e$ and $f$ cross.

Conversely, suppose that every diagonal in $E$ crosses an edge in $F$, and $G^{\prime }$ has a 2-cut $\{a,b\}$. Then $\{a,b\}$ is already a 2-cut in $G$, so $ab$ is a diagonal, and $G-ab$ has exactly two connected components. However, an edge $f\in F$ that crosses $ab$ connects the two components, contradicting the assumption that $\{a,b\}$ is a 2-cut in $G^{\prime }$.

If $G^{\prime }$ is 4-connected, then the two endpoints of a diagonal $ab\in E$ and an endpoint of a crossing edge $cd\in F$ cannot form a 3-cut. This leaves us with two possibilities: either $c$ or $d$ is the only vertex in one of the components of $G-ab$ (in this case $ab$ is an ear), or there an edge in $f_1\in F$ that crosses $ab$ and not incident to $c$, and an edge $f_2\in F$ that crosses $ab$ and not incident to $d$. Now if $f_1=f_2$, then $cd$ and $f_1=f_2$ are disjoint, otherwise $f_1$ and $f_2$ are disjoint. In both cases, two disjoint edges in $F$ cross $ab$.

Conversely, suppose that $G^{\prime }$ satisfies the conditions above but has a 3-cut $\{a,b,c\}$. If none of $ab$, $ac$ and $bc$ is diagonal in $E$, then $G-\{a,b,c\}$ is connected, so $\{a,b,c\}$ would not be a 3-cut. First, assume that $ab$, $ac$, and $bc$ are all diagonal in $G$. Then $G-\{a,b,c\}$ has exactly three components. However each edge of $\mathrm{\Delta }(a,b,c)$ crosses two edges in $F$, and in particular at least one edge that is not incident to $\{a,b,c\}$. Thus, each of the three components of $G-\{a,b,c\}$ is connected to another component in $G^{\prime }$, and so $G^{\prime }-\{a,b,c\}$ is connected.

Next, assume that only one edge of $\mathrm{\Delta }(a,b,c)$, say $ab$, is a diagonal of $E$. Then $G-\{a,b,c\}$ has exactly two components, separated by the line spanned by $ab$. In particular, if $ab$ is an ear, then $c$ cannot be the only vertex on one side of the line spanned by $ab$. In this case, $ab$ crosses at least two edges $f_1,f_2\in F$. At most one of them is incident to $c$: This is clear if $ab$ is not an ear, and $f_1,f_2$ are disjoint. If $ab$ is an ear, then $f_1,f_2$ are incident to a single vertex on one side of $ab$, but this vertex is not $c$, and so one of $f_1$ and $f_2$ is not incident to $c$. Since $F$ contains an edge between the two components of $G-\{a,b,c\}$, then $G^{\prime }$ is connected. $◀$

Let $e_0$ be an arbitrary edge of the convex hull of $V$, and let $E_0$ be the subset of $E$ comprising $e_0$ and all diagonals in $E$. We define a partial order $⪯$ on $E_0$: We say that $e⪯f$ if both $f$ and $e_0$ are in the same closed halfplane of bounded by the line spanned by $e$. (In particular, $e⪯e_0$ holds for all $e\in E_0$. The poset $(E_0,⪯)$ defines a tree, rooted at $e_0$, which is binary tree rooted at $e_0$. For a dynamic programming algorithm, we define the subproblems that correspond to the edge $e\in E_0$.

For an edge $e\in E_0$, integer $q\in \{0,\mathrm{\dots },\mathrm{\ell }\}$ and a vector $\overrightarrow{c}\in {\{1,\mathrm{\dots },\mathrm{\ell }\}}^q$, let ${\text{OPT}}_3(e,q,\overrightarrow{c})$ denote the minimum size of a set of new edges $F$ such that $G^{\prime }=(V,E\cup F)$ has the following properties:

• $\mathrm{■}$

  Edge $e$ crosses exactly $q$ edges in $F$: $f_1,\mathrm{\dots },f_q$;

• $\mathrm{■}$

  for $i=1,\mathrm{\dots },q$, edge $f_i\in F$ crosses at most $c_i$ edges $h\in E_0$, $h⪯e$; and

• $\mathrm{■}$

  every edge $h\in E_0$, $h⪯e$, crosses an edge in $F$ (cf. Proposition 7.1 for $k=3$).

If no such set $F$ exists, then we set ${\text{OPT}}_3(e,q,vecc)=\mathrm{\infty }$.

Our DP algorithm considers all edges $e\in E_0$ in increasing order in the poset $(E_0,⪯)$. If $e$ is a minimal element of the poset $(E_0,⪯)$, then $e$ is an ear, and ${\text{OPT}}_3(e,q,\overrightarrow{c})=q$ for all $\overrightarrow{c}$; see Figure 12(a). If $e$ is not minimal, then we may assume that $e=ab$ in a triangle $\mathrm{\Delta }(a,b,c)$, where $e_1=ac$ or $e_2=bc$ is also a diagonal in $E_0$. To compute ${\text{OPT}}_3(e,q,\overrightarrow{c})$, we compare all possibilities in the triangle $\mathrm{\Delta }(a,b,c)$ by brute force: Each of the $q$ edges that cross $e$ may cross $e_1$ or $e_2$, or end at vertex $c$. Furthermore, any edge that crosses $e_1$ (resp., $e_2$) may end at $b$ (resp., $a$) or cross $e$ or $e_2$ (resp., $e_1$). For each combination, we determine whether they are feasible (i.e., satisfy all constraints), and let ${\text{OPT}}_3(e,p,\overrightarrow{c})$ be the minimum size of a feasible solution; see Figure 12(b). Importantly, the order in which $e$ crosses $f_1,\mathrm{\dots },f_q$ is not specified – we count only unavoidable crossings: The edges in $\{f_1,\mathrm{\dots }{f}_q\}$ that are incident to $c$ must cross all edges that cross both $e_1$ and $e_2$, or cross $e_1$ and end at $b$, or cross $e_2$ and end at $a$. Similar conditions hold for edges that cross $e_1$ or $e_2$ by symmetry.

In this case, the combinatorial characterization in Proposition 7.1 is more involved, and we need to maintain information for bundles of new edges that cross an old edge. For an edge $e\in E_0$, integer $q\in \{0,\mathrm{\dots },\mathrm{\ell }\}$, vector $\overrightarrow{c}\in {\{1,\mathrm{\dots },\mathrm{\ell }\}}^q$, and a laminar set system $P$ over $\{1,\mathrm{\dots },q\}$, let ${\text{OPT}}_4(e,q,\overrightarrow{c},P)$ denote the minimum size of a set of new edges $F$ such that $G^{\prime }=(V,E\cup F)$ has the following properties:

• $\mathrm{■}$

  Edge $e$ crosses exactly $q$ edges in $F$: $f_1,\mathrm{\dots },f_p$;

• $\mathrm{■}$

  for $i=1,\mathrm{\dots },p$, edge $f_i\in F$ crosses at most $c_i$ edges $h\in E_0$, $h⪯e$;

• $\mathrm{■}$

  each set $S\in P$ corresponds to a set $F_{e,S}=\{f_i:i\in S\}$ such that the edges in $F_{e,S}$ have a common endpoint below $e$ or $F_{e,S}$ is the set of all edges in $F$ that cross an edge $h⪯e$;

• $\mathrm{■}$

  every edge $h\in E_0$, $h⪯e$, satisfies the conditions in Proposition 7.1 for $k=4$ assuming the edges in each set $F_{e,S}$, $S\in P$, do not have a common endpoint above $e$.

If no such set $F$ exists, then we set ${\text{OPT}}_4(e,q,\overrightarrow{c},P)=\mathrm{\infty }$.

Our DP algorithm considers all edges $e\in E_0$ in increasing order in the poset $(E_0,⪯)$. If $e$ is a minimal element of the poset $(E_0,⪯)$, then $e$ is an ear. In this case, all edges that cross $e$ must have a common endpoint below $e$: We set ${\text{OPT}}_3(e,q,\overrightarrow{c},P)=q$ for all $\overrightarrow{c}$ if $P=\{\{1,\mathrm{\dots }q\}\}$, and ${\text{OPT}}_3(e,q,\overrightarrow{c},P)=\mathrm{\infty }$ for any other partition $P$; see Figure 12(a). If $e$ is not minimal, then $e=ab$ in a triangle $\mathrm{\Delta }(a,b,c)$, where $e_1=ac$ or $e_2=bc$ is also a diagonal in $E_0$. We compute ${\text{OPT}}_4(e,q,\overrightarrow{c},P)$ by a brute force comparison of all possible subproblems for edges $e_1$ and $e_2$. By maintaining the laminar system $P$, we can determine whether every non-ear edge is crossed by at least two disjoint edges. $◀$

We may assume w.l.o.g. that the input is a triangulation $G$ on $n$ points in convex position. The dual graph is a binary tree with $n$ nodes. We can partition the dual tree into subtrees (clusters) of size in the range $[k,3k]$. Each cluster is a union of triangles, i.e., a convex polygon with $\mathrm{\Theta }(k)$ vertices. The adjacency graph of the clusters (cluster graph) is a tree of maximum degree $O(k)$.

We can augment $G$ as follows. (1) Augment each cluster to a complete graph; (2) for each pair of adjacent clusters $V_1$ and $V_2$ (where $|V_1\cap V_2|=2$) add a matching of size $k-2$ between $V_1\setminus V_2$ and $V_2\setminus V_1$. Let $G^{\prime }$ be the augmented graph. Similarly to the proof of Theorem 3.2, the geometric graph graph $G^{\prime }$ is $k$-connected (by induction on the clusters), and $O(k^2)$-planar (arguing about edges induced by a cluster, and a pair of adjacent clusters). $◀$