Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

The proof is by a polynomial-time reduction from 3-SAT. We shall use two types of gadgets: $2$-permuters for variable assignment and $3$-permuters for clause verification (see Fig. 7). For simplicity, each $k$-permuter is depicted by a black box on the diagram, where the value of $k$ is made clear by the number of incoming/outgoing paths. Each different colour in the figure indicates a different variable. The thick or thin dashed lines on the top, bottom and middle-left part of the diagram indicate respectively the false and true literals of each variable. The thick and thin solid lines in the middle-right section of the diagram indicate respectively the true or false assignment of each variable. Given a Boolean formula in 3-CNF form with $n$ variables, we construct $2n$ non-crossing semi-circular arcs. We replicate this construction twice to form the top and bottom parts of the diagram. In the middle, we show a single clause gadget, involving two $3$-permuters. To simulate the two logical OR of the clause, we proceed as follows: if the corresponding $3$-clause involves the variables $x_i$, $x_j$ and $x_k$, we select the wire opposite to their desired truth value in the clause (i.e. thick for $\overline{x_i}$, thin for $x_i$) and “drag” them towards the gadget to intersect the same single path chosen among the three paths linking the output of the first $3$-permuter to the inputs of the second. By construction, there is no valid permutation assignment to the two $3$-permuters which avoids all possible self-intersections with the three black paths if and only if $x_i$, $x_j$ and $x_k$ all have the wrong truth assignment. Furthermore, to the right of the $3$-clause gadget, we have weaved the incoming paths of the first and the outgoing paths of the second in such a way that, if the composition of the two $3$-permuters were not the identity, at least one of the resulting closed loop would self-intersect. Thus each such pair of $3$-permuters cannot “cheat” and has to compose to the identity. As a consequence, for each of the variables involved, the composition of its two $2$-permuters must also be the identity. By construction, there are then exactly two ways of ensuring this is the case: either both $2$-permuters are the identity themselves (setting the variable to be true), or both of them correspond to the transposition $(12)$ swapping the inputs (setting the variable to be false). Fig. 8 shows the instance created for the Boolean formula $(\overline{x_1}\vee x_2\vee x_3)\wedge (\overline{x_4}\vee x_5\vee \overline{x_6})$. $◀$

The proof of the claim proceeds as follows: we first construct self-intersection gadgets to simulate $2$-permuters, take note of the fact that $S_n$ is generated by transpositions and show how to use $2$-permuters to construct general $k$-permuters. The construction for $2$-permuters is presented on Fig. 9: the inputs and outputs are connected by two curves weaved into a double coil structure with two intersections, one of which is a switch. The three resulting configurations are shown on the figure; only the leftmost two are free of self-intersections.

To simulate a general $k$-permuter, we introduce the gadget illustrated in Fig. 10. We begin with a $k$-by-$k$ square and evenly distribute $k$ inputs and outputs on its top and bottom edges, respectively. For every $i\in [n]$, the top $i$-th input is connected to the bottom $(n-i)$-th output by the path of slope $-1$ which gets reflected into a path of slope $1$ upon meeting the left edge of the square. We then insert a total of $\frac{k(k-1)}{2}$ $2$-permuters: one at every site where two paths intersect inside the square.

While many configurations of this gadget are redundant and yield the same permutation, a short inductive argument shows that it is indeed able to simulate any permutation on $k$ elements. The base case is simply the $2$-permuter we previously described. Assume then by induction that the version of our gadget with $k-1$ inputs and outputs can successfully simulate all permutations of $[k-1]$. Note that any permutation $\sigma$ of $[k]$ can be written as the composition of a permutation of $[k-1]$ followed by the insertion of the element $k$ into one of the $k$ positions before or after one of the $k-1$ permuted elements. It is thus enough to show that the addition of the last “row” of $k-1$ $2$-permuters (highlighted in pink) can simulate this last insertion step. Labelling the $(k-1)$ $2$-permuters of the $(k-1)$-th row according to the direction indicated on Fig. 10, we insert the element $k$ in position $i$ (before the $i$-th element) by setting all the $2$-permuters from positions $i$ to $k$ to swap their inputs, and the remaining $i$ $2$-permuters to the identity. This effectively shifts all the elements with positions greater than $i$ by $1$ (the permuters reroute their corresponding wires to the segment of slope $1$ instead of $-1$) as we sequentially shift the element $k$ to the left $i$ times (the permuters successively let the $k$-th input path “slide” on the last path of slope $-1$). $◀$

Theorem 3 now follows directly from Theorem 4 and Lemma 5. $◀$

We introduce the Bruxelles waffle (in contrast to the Liège waffle which we describe in Section 2.2.3). The construction is illustrated in Figure 11.

Assume that after fewer than $c$ switches, no self-intersections remain. We need to show that opposite terminals lie on the same strand. Assume for a contradiction that opposite terminals do not lie on the same strand. Then the left terminal lies on the same strand as either the top or the bottom terminal. Without loss of generality (by rotational symmetry of the gadget) assume that the left terminal lies on the same strand as the bottom terminal.

Because there are $c$ rows, at least one row has not undergone any switch, and the horizontal path in that row has a single color. Because there are no self-intersections, all strands crossing the row vertically have a color different from the horizontal path of the row. Removing the row splits the gadget into a part above and a part below the row, and the left and right endpoints of the horizontal path connect to different such parts. The strand containing the horizontal path of the row cannot be closed up without crossing the row, so the strand connects a terminal below and a terminal above the row. That is, it connects the bottom or left terminal to the top or right terminal. This contradicts our assumption that the bottom and left terminals lie on the same strand. $◀$

We introduce the Liège waffle, illustrated in Figure 13.

Essentially, we overlay $c$ new closed curves on the two (crossing) terminal strands, such that each of the new curves is incident to each of the four unbounded faces, and that the disk bounded by the curve contains the crossing between the two terminal strands.

If we change the global connectivity, then one of the four unbounded faces will globally have two strands of the same curve; say the top left face (Figure 13 (c)). In order for this face to not be popular, these two strands must be consecutive along the curve. Initially, all intersections incident to the face are crossing, so they must all be uncrossed. There are $c+1$ such intersections, so we need at least $c+1$ switches. $◀$

We first show that Item 2 rules out Item 1. Let $C$ be a component of $G-v$ that does not touch the boundary and without loss of generality assume that it contains $v_1$ (otherwise relabel the $v_i$’s). Because $C$ does not touch the boundary, the vertices of $C$ of degree $1$ form a subset of $\{v_1,v_2,v_3,v_4\}$. Because $v$ is a cut-vertex of $G$, there exists some $v_i$, $i\in \{2,3,4\}$ that does not lie in $C$. By the handshaking lemma, $C$ contains exactly two vertices of degree $1$.

We claim that $C$ does not contain $v_3$. Suppose for a contradiction that $C$ contains $v_3$, then the path from $v_1$ to $v_3$ corresponds to a cycle $c$ through $v$ in $G$ that by the Jordan curve theorem separates the components $C_2$ and $C_4$ containing $v_2$ and $v_4$ respectively, so $C_2\ne C_4$. By the handshaking lemma, $C_2$ and $C_4$ must have an odd (and therefore nonzero) number of boundary ports (to compensate for the vertex $v_2$ or $v_4$ of degree $1$). However, $C_2$ or $C_4$ lies interior to the disk bounded by $c$ and hence has no boundary ports, which is a contradiction, so $C$ does not contain $v_3$.

Assume without loss of generality that $C$ contains $v_1$ and $v_2$ (the argument for $v_1$ and $v_4$ is symmetric). Now, if the Eulerian partition of $G$ that was straight at $v$ is simple, then $G-v$ must contain an Eulerian partition that does not contain a path connecting $v_1$ to $v_2$ (otherwise the path would self-intersect at $v$ in $G$). However, because these are the only vertices of $C$ of degree $1$, and Eulerian partition of $G-v$ contains such a path, so Item 2 rules out Item 1.

It remains to construct a simple Eulerian partition (that is straight at $v$) if $v$ is not a cut-vertex, or if all components of $G-v$ incident to $v_i$ ($i\in \{1,\mathrm{\dots },4\}$) touch the boundary. Let $C_i$ ($i=1,\mathrm{\dots },4$) be the component of $G-v$ containing $v_i$. We first show that there exists a simple Eulerian partition that is straight at $v$ if $C_1=C_3$ (and by symmetric argument if $C_2=C_4$). Assume that $C_1=C_3$, then $G-v$ contains a simple path ${\pi }_1$ from $v_1$ to $v_3$. Let $G-v-{\pi }_1$ be the graph obtained from $G-v$ by removing the edges of ${\pi }_1$. If $v_2$ and $v_4$ are connected in $G-v-{\pi }_1$, then there exists a simple path ${\pi }_2$ from $v_2$ to $v_4$. Then ${\pi }_1$ and ${\pi }_2$ correspond to simple cycles $c_1$ and $c_2$ in $G$ that are straight at $v$, and the remainder of $G$ admits a Eulerian partition (and hence a simple one). If instead $v_2$ and $v_4$ are not connected after removing the edges of ${\pi }_1$ from $G-v$, then we pick an arbitrary Eulerian partition of $G-v-{\pi }_1$. This partition corresponds to a partition of $G$ in which ${\pi }_1$ corresponds to a simple cycle that is straight at $v$, and the paths that contain $v_2$ and $v_4$ (call them ${\pi }_2$ and ${\pi }_4$) do not intersect because they lie in different components of $G-v-{\pi }_1$. Hence, the paths ${\pi }_2$ and ${\pi }_4$ can be concatenated by replacing the end points $v_2$ and $v_4$ by the vertex $v$ in $G$, to obtain a simple path in $G$ that is straight at $v$.

We have established that there exists a simple Eulerian partition that is straight at $v$ if $C_1=C_3$ or $C_2=C_4$, so assume that $C_1\ne C_3$ and $C_2\ne C_4$. Then $v$ is a cut-vertex, so it remains to show that if each $C_i$ touches the boundary, then there exists a simple Eulerian partition that is straight at $v$. We claim that $G-v$ contains edge-disjoint simple paths ${\pi }_i$ ($i=1,\mathrm{\dots },4$) that connect each $v_i$ to the boundary. For this, let ${\pi }_1$ and ${\pi }_3$ be arbitrary simple paths and consider the component $C_2^{\prime }$ of $G-v-{\pi }_1-{\pi }_3$ that contains $v_2$. We claim that this component contains a boundary vertex. Indeed, by the handshaking lemma, $C_2^{\prime }$ contains an even number of vertices of degree $1$, and one of them is $v_2$. None of the vertices $v_1$, $v_3$, $v_4$ lie in $C_2^{\prime }$, because $v_1$ and $v_3$ were isolated by removing the edges of ${\pi }_1$ and ${\pi }_3$, and $v_4$ lies on a different component because $C_2\ne C_4$. Hence, $C_2^{\prime }$ contains a boundary vertex, and hence a simple path ${\pi }_2$ to it from $v_2$. By a symmetric argument, a component of $G-v-{\pi }_1-{\pi }_3$ contains a simple path ${\pi }_4$ from $v_4$ to a boundary vertex. Because $C_1\ne C_3$ and $C_2\ne C_4$, the “concatenations” of ${\pi }_1$ with ${\pi }_3$ and of ${\pi }_2$ with ${\pi }_4$ in $G$ are simple and straight at $v$. The remainder of $G$ (after removing these two paths) admits a Eulerian partition and hence a simple one. Reinserting the two paths yields a simple Eulerian partition of $G$ that is straight at $v$. $◀$

This now leads to the following result:

Suppose we have an arrangement $𝒜$ for which the answer is yes, and let $G$ be its (planar) graph. $G$ has one special vertex $\xi$ that represents the non-switchable crossing. We augment $G$ by adding a new vertex $\omega$ that represents the outer face; we create an edge from all vertices on the frame to $\omega$ Now consider a configuration $K$ for $𝒜$ without self-intersections. All curves in $𝒜$ are now edge-disjoint cycles in $G$. Now, consider the cycles that pass through $\xi$. Note that these must be two cycles; we will refer to them as the red cycle and blue cycle.

Now, replace $\xi$ by four degree $1$ vertices that we refer to as terminals. Let $G^{\prime }$ be the resulting (planar) graph. Note that now, we have a red and a blue path in $G^{\prime }$, and the paths incident to opposing terminals have the same color.

Now, our goal is to test whether such a configuration $K$ can exist, based only on the information in $G$. That is, we need to find whether there exist two edge-disjoint paths in $G^{\prime }$ that connect opposite pairs of terminals. The existence of edge-disjoint paths that connect two pairs of terminals can be tested in $O(n^2)$ time [13].

If so, by Lemma 14, we then have a Eulerian partition of the remainder, and we can cover it by edge-disjoint cycles. In addition, when we re-insert $\xi$, the two paths become an edge-disjoint red and blue cycle that are straight at $\xi$. $◀$

The proof of Theorem 15 is constructive, and leads to the following algorithm:

Suppose we have an arrangement $𝒜$ for which the answer is yes, and let $G$ be its (planar) graph. We augment $G$ by adding a new vertex $\omega$ that represents the outer face; we create an edge from all vertices on the frame to $\omega$ Now consider a configuration $K$ for $𝒜$ without self-intersections. All curves in $𝒜$ are now edge-disjoint cycles in $G$.

Consider the cycles that pass through at least one non-switchable crossing. Because each non-switchable crossing involves only two cycles, there are at most $2k$ such cycles, and we will assign distinct colors to these cycles.

Replace each non-switchable crossing by four terminals corresponding to the four incident edges. Let $G^{\prime }$ be the resulting graph. This cuts up the cycles that pass through the non-switchable crossings into exactly $2k$ edge-disjoint colored paths that each start and end at terminals. For each non-switchable crossing, the paths incident to opposing terminals have the same color. On the other hand, because any cycle passes through any non-switchable crossing only once, every non-switchable crossing is incident to two distinct colors, so any two of its terminals that are not opposing have different colors.

We wish to recover a configuration $K^{\prime }$ without self-intersections for $G$ based on only the following information derived from $K$:

1. 1.

   the pairs of terminals that are connected by the $2k$ edge-disjoint paths; and

2. 2.

   for each such pair, the color of the path that connects them.

For a given graph, one can decide the existence of edge-disjoint paths that connect specified pairs of terminals (and report the paths if they exist) in $O(k^{k^{k^{k^{k^{{\mathrm{\dots }}^k}}}}}\cdot n^2)$ time [13]. If we apply this algorithm to $G^{\prime }$ with the above information derived from $K$, it will return that there exists a set of edge-disjoint paths.

For any such set of edge-disjoint paths, we can correspondingly color the edges of $G$, and give all the edges that do not lie on any of the $2k$ paths a new color (e.g. color $2k+1$). This results in an Eulerian partition of $G$ that is straight at each of the non-switchable crossings. Any switch will either be incident to four edges of the same color, or two pairs of two edges with the same color. We now define our configuration $K^{\prime }$ as follows. If the four edges incident to a switch $s$ have the same color, we configure $s$ so as not to create a crossing. If on the other hand, $s$ is incident to two pairs of edges with different colors, we configure $s$ in the obvious way: connecting both pairs of edges with the same color. Now, each strand of $K^{\prime }$ has a single color. We show that no strand of $K^{\prime }$ intersects itself. Indeed, any self-intersection must occur at a vertex incident to four edges of the same color. Because non-switchables are not incident to four edges of the same color, the only vertices at which a strand might self-intersect is at a switch. However, by construction, switches whose four incident edges all have the same color are configured not to cross. Hence, configuration $K^{\prime }$ has no self-intersections. $◀$

Again, the proof is constructive; we now have all the ingredients for our main algorithm:

The above ideas can be partially extended to the case of removing popular faces. However, the general question whether removing popular faces is FPT in the number of non-switchable crossings remains open.