The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles

From properties (i), (ii) and (iii) it follows that the parity of the number of crossings between $({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}})$ and $({\gamma }^{\mathrm{out}},{\delta }^{\mathrm{in}})$ depends only on the inside/outside decisions at the vertices ${\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}},{\gamma }^{\mathrm{out}}$ and ${\delta }^{\mathrm{in}}$. This means that it is enough to check a single drawing for each set of inside/outside decisions that are allowed by the claim. The proof follows by a case analysis that is easy to verify by inspection, see Figure 8 for illustrations of the possible cases.

$◀$

It remains to prove that the drawing of $G$ satisfies the conditions stated in Proposition 8. Conditions (A) and (C) are shown to hold in Proposition 9 while (B) is handled in Proposition 10. Note that in Condition (C) there is a symmetry between the two edges, namely, the cyclic order can also be written as $({\gamma }^{\mathrm{out}},{\beta }^{\mathrm{in}},{\alpha }^{\mathrm{out}},{\delta }^{\mathrm{in}})$. Therefore it is enough to prove, say, that $d({\gamma }^{\mathrm{out}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))\ne d({\beta }^{\mathrm{in}},({\gamma }^{\mathrm{out}},{\delta }^{\mathrm{in}}))$ holds for the given cyclic order of the endpoints, this is shown in the following Proposition 9.

Orient $\beta$ and $\gamma$ such that they enter the interior of $c$ at ${\beta }^{\mathrm{in}}$ and ${\gamma }^{\mathrm{out}}$, respectively (recall that $\beta \ne \gamma$). We will show that if $d({\gamma }^{\mathrm{out}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))=2$, then $d({\beta }^{\mathrm{in}},({\gamma }^{\mathrm{out}},{\delta }^{\mathrm{in}}))=1$. A symmetric argument (reflect the arrangement and switch the role of $\beta$ and $\gamma$ and also of $\alpha$ and $\delta$) shows that if $d({\beta }^{\mathrm{in}},({\gamma }^{\mathrm{out}},{\delta }^{\mathrm{in}}))=1$, then $d({\gamma }^{\mathrm{out}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))=2$. Together, these two assertions imply the claim.

Suppose that $d({\gamma }^{\mathrm{out}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))=2$. This means that as we follow $\gamma$ starting from ${\gamma }^{\mathrm{out}}$ it intersects $\beta$ before it intersects $\alpha$. Let $x$ denote this first intersection point of $\gamma$ and $\beta$ (see Figure 9). We will show that ${[{\beta }^{\mathrm{in}},x]}_{\beta }$ does not intersect $\delta$, and hence $d({\beta }^{\mathrm{in}},({\gamma }^{\mathrm{out}},{\delta }^{\mathrm{in}}))=1$.

Let $t$ be the closed curve which consists of ${[{\gamma }^{\mathrm{out}},x]}_{\gamma }$, ${[{\beta }^{\mathrm{in}},x]}_{\beta }$ and ${[{\gamma }^{\mathrm{out}},{\beta }^{\mathrm{in}}]}_c$. We claim that $t$ is a simple curve that is not crossed by any of $\alpha$, $\beta$, and $\gamma$.

Consider first $\beta$ and observe that it does not cross itself nor can it cross ${[{\gamma }^{\mathrm{out}},x]}_{\gamma }$ by the definition of $x$. From Proposition 6, it follows that ${\beta }^{\mathrm{out}}\in {({\beta }^{\mathrm{in}},{\alpha }^{\mathrm{out}})}_c$ and therefore $\beta$ does not cross ${[{\gamma }^{\mathrm{out}},{\beta }^{\mathrm{in}}]}_c$, and hence it does not cross $t$.

Next, consider $\gamma$ and observe that it does not cross itself nor can it cross ${[{\gamma }^{\mathrm{out}},{\beta }^{\mathrm{in}}]}_c$ since it follows from Proposition 6 that ${\gamma }^{\mathrm{in}}\in {({\delta }^{\mathrm{in}},{\gamma }^{\mathrm{out}})}_c$. Therefore, $t$ is a simple curve (recall that $\beta$ and ${({\gamma }^{\mathrm{out}},x)}_{\gamma }$ cannot intersect by the definition of $x$). Let $T$ be the “triangular” region which is bounded by $t$ and is to the right of $\gamma$ (and to the left of $\beta$ and $c$).

Returning to $\gamma$, it remains to show that it cannot intersect ${({\beta }^{\mathrm{in}},x)}_{\beta }$. Suppose for contradiction that it does intersect ${({\beta }^{\mathrm{in}},x)}_{\beta }$ at a point $y$. Then either $\gamma$ enters $T$ at $y$ or it leaves $T$ at $y$. In the first case, following $\gamma$ from $y$, it must leave $T$ since the part of $\gamma$ just before ${\gamma }^{\mathrm{out}}$ lies outside $T$. However, this means that $\gamma$ must cross $t$ and hence ${({\beta }^{\mathrm{in}},x)}_{\beta }$ at another point which is impossible since $\beta$ and $\gamma$ already intersect at $x$ and $y$, see Figure 9(a).

Considering the second case, if $\gamma$ leaves $T$ at $y$, then it implies that $\gamma$ enters $T$ at $x$, which in turn implies that $\beta$ is also entering $T$ at $x$ (otherwise $\beta$ and $\gamma$ would touch at $x$ which is impossible), see Figure 9(b). However, following $\beta$ from $x$, we would have to cross $t$ since the part of $\beta$ just before ${\beta }^{\mathrm{in}}$ lies outside $T$. Since we have already observed that $\beta$ does not cross $t$ we conclude that $\gamma$ does not cross $t$ either.

We now show that $\alpha$ cannot intersect $t$. By the definition of $x$ it cannot intersect ${[{\gamma }^{\mathrm{out}},x]}_{\gamma }$. By Proposition 6 we have ${\alpha }^{\mathrm{in}}\in {({\beta }^{\mathrm{in}},{\alpha }^{\mathrm{out}})}_c$ and it follows that $\alpha$ cannot intersect ${[{\gamma }^{\mathrm{out}},{\beta }^{\mathrm{in}}]}_c$. Finally, if $\alpha$ crosses ${[{\beta }^{\mathrm{in}},x]}_{\beta }$, then it must cross it twice since $\alpha$ does not cross the other parts of $t$. The digon formed by $\alpha$ and $\beta$ must lie outside of $T$ since $T$ lies outside the digon-region of $\beta$. Consequently, apart from its subarc that bounds this digon $\alpha$ is contained in $T$. However, this is impossible since then $\gamma$ and $\alpha$ do not intersect.

We are now ready to show that $\delta$ cannot intersect ${[{\beta }^{\mathrm{in}},x]}_{\beta }$ which would imply that $d({\beta }^{\mathrm{in}},({\gamma }^{\mathrm{out}},{\delta }^{\mathrm{in}}))=1$. Assume to the contrary that $\delta$ intersects ${[{\beta }^{\mathrm{in}},x]}_{\beta }$. Notice that ${\delta }^{\mathrm{in}},{\delta }^{\mathrm{out}},{\gamma }^{\mathrm{out}}$, and ${\beta }^{\mathrm{in}}$ appear in this cyclic order on $c$. This follows from Proposition 6 and the assumptions of the claim. This implies that $\delta$ does not intersect ${[{\gamma }^{\mathrm{out}},{\beta }^{\mathrm{in}}]}_c$. It follows that the two simple closed curves $\delta$ and $t$ must either cross twice or four times, since crossing six times or more would imply that $\delta$ intersects $\gamma$ or $\beta$ more than twice. If $\delta$ and $t$ cross four times, then $\delta$ crosses twice each of ${[{\beta }^{\mathrm{in}},x]}_{\beta }$ and ${[{\gamma }^{\mathrm{out}},x]}_{\gamma }$. Therefore, the only part of $\delta$ that is outside the digon-region of $\gamma$ and the digon-region of $\beta$ must be in $T$. The curves $\alpha$ and $\delta$ cannot cross in the digon-region of $\gamma$, because $\delta$ and $\gamma$ form a digon. Similarly, $\alpha$ and $\delta$ cannot cross in the digon-region of $\beta$ because $\alpha$ and $\beta$ form a digon. Since $\alpha$ is disjoint from $T$ we conclude that $\alpha$ and $\delta$ do not intersect which is a contradiction. We reach a similar contradiction in the case where $\delta$ crosses $t$ precisely at two points that happen to be on ${[{\beta }^{\mathrm{in}},x]}_{\beta }$, once again $\alpha$ and $\delta$ cannot intersect.

It remains to consider the case where $\delta$ crosses ${[{\beta }^{\mathrm{in}},x]}_{\beta }$ once and crosses ${[{\gamma }^{\mathrm{out}},x]}_{\gamma }$ once. The latter implies that either $x$ or ${\gamma }^{\mathrm{out}}$ belong to the digon formed by $\delta$ and $\gamma$, which is impossible since neither $\beta$ nor $c$ intersects this digon. $◀$

Orient $\gamma$ and $\delta$ such that they enter the interior region of $c$ at ${\gamma }^{\mathrm{out}}$ and ${\delta }^{\mathrm{in}}$, respectively. Recall that $c$ is oriented counterclockwise and its interior region lies to its left. Thus, the digon-region of $\gamma$ lies to its left whereas the digon-region of $\delta$ lies to its right. Let $\{A_1^{\prime },A_2^{\prime }\}=\delta \cap \alpha$ and $\{B_1^{\prime },B_2^{\prime }\}=\delta \cap \beta$, such that the cyclic order of these four points along $\delta$ is $A_1^{\prime },A_2^{\prime },B_1^{\prime },B_2^{\prime }$ (since $\alpha$ and $\beta$ form a digon it follows from Proposition 6 that $A_1^{\prime }$ and $A_2^{\prime }$ must be consecutive and so are $B_1^{\prime }$ and $B_2^{\prime }$). Similarly, let $\{A_1^{\prime \prime },A_2^{\prime \prime }\}=\gamma \cap \alpha$ and $\{B_1^{\prime \prime },B_2^{\prime \prime }\}=\gamma \cap \beta$, such that the cyclic order of these four points along $\gamma$ is $A_1^{\prime \prime },A_2^{\prime \prime },B_1^{\prime \prime },B_2^{\prime \prime }$.

Considering the cyclic order of $A_1^{\prime },A_2^{\prime },A_1^{\prime \prime }$ and $A_2^{\prime \prime }$ along $\alpha$ (under some orientation of $\alpha$), it follows from Proposition 6 that the first two are consecutive and so are the last two (since $\gamma$ and $\delta$ form a digon). Therefore, if we orient $\alpha$ such that $A_2^{\prime }$ follows $A_1^{\prime }$, then the cyclic order of those four points is either $A_1^{\prime },A_2^{\prime },A_1^{\prime \prime },A_2^{\prime \prime }$ or $A_1^{\prime },A_2^{\prime },A_2^{\prime \prime },A_1^{\prime \prime }$.

We claim that the former is impossible. Indeed, suppose that $A_1^{\prime },A_2^{\prime },A_1^{\prime \prime }$ and $A_2^{\prime \prime }$ appear in this cyclic order on $\alpha$. Note that it follows from the cyclic order on $\delta$ (resp., $\gamma$) that both of $B_1^{\prime }$ and $B_2^{\prime }$ (resp., $B_1^{\prime \prime }$ and $B_2^{\prime \prime }$) must be in the same region (interior or exterior) of $\alpha$. If $B_1^{\prime },B_2^{\prime },B_1^{\prime \prime }$ and $B_2^{\prime \prime }$ are in the exterior of $\alpha$, then either ${[A_1^{\prime \prime },A_2^{\prime \prime }]}_{\alpha }$ or ${[A_1^{\prime },A_2^{\prime }]}_{\alpha }$ is contained in the intersection of the digon-regions of $\gamma$ and $\delta$ (see Figure 10), which is impossible.

By a symmetric argument, it is impossible that $B_1^{\prime },B_2^{\prime },B_1^{\prime \prime }$, and $B_2^{\prime \prime }$ are in the interior of $\alpha$. Therefore, either $B_1^{\prime }$ and $B_2^{\prime }$ are in the digon-region of $\alpha$ or $B_1^{\prime \prime }$ and $B_2^{\prime \prime }$ are there. However, this implies that the subarc of $\beta$ in the digon-region of $\alpha$ intersects either $\gamma$ or $\delta$ which is impossible since $\alpha$ and $\beta$ form a digon.

Thus $A_1^{\prime },A_2^{\prime },A_2^{\prime \prime },A_1^{\prime \prime }$ appear in this cyclic order on $\alpha$, and similarly, $B_1^{\prime },B_2^{\prime },B_2^{\prime \prime },B_1^{\prime \prime }$ appear in this cyclic order on $\beta$ if it is oriented such that $B_2^{\prime }$ immediately follows $B_1^{\prime }$. Next, we redraw $\alpha$ close to the digon it forms with $\beta$ such that these two pseudocircles become disjoint (see Figure 11). In a similar way, we redraw $\delta$ such that $\delta$ and $\gamma$ become disjoint. Note that no other intersection points but $\alpha \cap \beta$ and $\gamma \cap \delta$ are destroyed and no new intersection points are introduced. Therefore, the vertex set of $𝒜(\{\alpha ,\beta ,\gamma ,\delta \})$ is precisely $\{A_1^{\prime },A_2^{\prime },A_1^{\prime \prime },A_2^{\prime \prime },B_1^{\prime },B_2^{\prime },B_1^{\prime \prime },B_2^{\prime \prime }\}$ and its edge set consists of the edges ${[A_1^{\prime },A_2^{\prime }]}_{\alpha }$, ${[A_2^{\prime },A_2^{\prime \prime }]}_{\alpha }$, ${[A_2^{\prime \prime },A_1^{\prime \prime }]}_{\alpha }$, ${[A_1^{\prime \prime },A_1^{\prime }]}_{\alpha }$, ${[B_1^{\prime },B_2^{\prime }]}_{\beta }$, ${[B_2^{\prime },B_2^{\prime \prime }]}_{\beta }$, ${[B_2^{\prime \prime },B_1^{\prime \prime }]}_{\beta }$, ${[B_1^{\prime \prime },B_1^{\prime }]}_{\beta }$, ${[A_1^{\prime \prime },A_2^{\prime \prime }]}_{\gamma }$, ${[A_2^{\prime \prime },B_1^{\prime \prime }]}_{\gamma }$, ${[B_1^{\prime \prime },B_2^{\prime \prime }]}_{\gamma }$, ${[B_2^{\prime \prime },A_1^{\prime \prime }]}_{\gamma }$, ${[A_1^{\prime },A_2^{\prime }]}_{\delta }$, ${[A_2^{\prime },B_1^{\prime }]}_{\delta }$, ${[B_1^{\prime },B_2^{\prime }]}_{\delta }$ and ${[B_2^{\prime },A_1^{\prime }]}_{\delta }$. It is not hard to see that this implies that the face set of $𝒜(\{\alpha ,\beta ,\gamma ,\delta \})$ consists of four digons whose boundaries are $\{{[A_1^{\prime },A_2^{\prime }]}_{\alpha },{[A_1^{\prime },A_2^{\prime }]}_{\delta }\}$, $\{{[A_1^{\prime \prime },A_2^{\prime \prime }]}_{\alpha },{[A_1^{\prime \prime },A_2^{\prime \prime }]}_{\gamma }\}$, $\{{[B_1^{\prime },B_2^{\prime }]}_{\beta },{[B_1^{\prime },B_2^{\prime }]}_{\delta }\}$ and $\{{[B_1^{\prime \prime },B_2^{\prime \prime }]}_{\beta },{[B_1^{\prime \prime },B_2^{\prime \prime }]}_{\gamma }\}$, and six faces of size four whose boundaries are (refer to Figure 11 for an illustration):
$\{{[A_1^{\prime },A_2^{\prime }]}_{\delta },{[A_2^{\prime },A_2^{\prime \prime }]}_{\alpha },{[A_2^{\prime \prime },A_1^{\prime \prime }]}_{\gamma },{[A_1^{\prime \prime },A_1^{\prime }]}_{\alpha }\}$, $\{{[A_1^{\prime },A_2^{\prime }]}_{\alpha },{[A_2^{\prime },B_1^{\prime }]}_{\delta },{[B_1^{\prime },B_2^{\prime }]}_{\beta },{[B_2^{\prime },A_1^{\prime }]}_{\delta }\}$,
$\{{[B_1^{\prime },B_2^{\prime }]}_{\delta },{[B_2^{\prime },B_2^{\prime \prime }]}_{\beta },{[B_2^{\prime \prime },B_1^{\prime \prime }]}_{\gamma },{[B_1^{\prime \prime },B_1^{\prime }]}_{\beta }\}$, $\{{[A_1^{\prime \prime },A_2^{\prime \prime }]}_{\alpha },{[A_2^{\prime \prime },B_1^{\prime \prime }]}_{\gamma },{[B_1^{\prime \prime },B_2^{\prime \prime }]}_{\beta },{[B_2^{\prime \prime },A_1^{\prime \prime }]}_{\delta }\}$,
$\{{[A_1^{\prime },A_1^{\prime \prime }]}_{\alpha },{[A_1^{\prime \prime },B_2^{\prime \prime }]}_{\gamma },{[B_2^{\prime \prime },B_2^{\prime }]}_{\beta },{[B_2^{\prime },A_1^{\prime }]}_{\delta }\}$ and $\{{[A_2^{\prime },A_2^{\prime \prime }]}_{\alpha },{[A_2^{\prime \prime },B_1^{\prime \prime }]}_{\gamma },{[B_1^{\prime \prime },B_1^{\prime }]}_{\beta },{[B_1^{\prime },A_2^{\prime }]}_{\delta }\}$.

Note that $d({\gamma }^{\mathrm{out}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))=1$ and $d({\delta }^{\mathrm{in}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))=2$ iff ${\gamma }^{\mathrm{out}}\in {(B_2^{\prime \prime },A_2^{\prime \prime })}_{\gamma }$ and ${\delta }^{\mathrm{in}}\in {(A_2^{\prime },B_2^{\prime })}_{\delta }$. Similarly, $d({\gamma }^{\mathrm{out}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))=2$ and $d({\delta }^{\mathrm{in}},({\alpha }^{\mathrm{out}},{\beta }^{\mathrm{in}}))=1$ iff ${\gamma }^{\mathrm{out}}\in {(A_2^{\prime \prime },B_2^{\prime \prime })}_{\gamma }$ and ${\delta }^{\mathrm{in}}\in {(B_2^{\prime },A_2^{\prime })}_{\delta }$. Suppose for contradiction that one of these cases holds. Then, on the one hand, there is a curve, namely ${[{\gamma }^{\mathrm{out}},{\delta }^{\mathrm{in}}]}_c$, which connects ${\gamma }^{\mathrm{out}}$ and ${\delta }^{\mathrm{in}}$ while not crossing any of $\alpha$, $\beta$, $\gamma$ and $\delta$ (this follows from the given cyclic order and Proposition 6). However, on the other hand, there is no face of $𝒜(\{\alpha ,\beta ,\gamma ,\delta \})$ whose boundary contains segments of both ${(B_2^{\prime \prime },A_2^{\prime \prime })}_{\gamma }$ and ${(A_2^{\prime },B_2^{\prime })}_{\delta }$ or segments of both ${(A_2^{\prime \prime },B_2^{\prime \prime })}_{\gamma }$ and ${(B_2^{\prime },A_2^{\prime })}_{\delta }$, contradicting the existence of a curve as above. $◀$

This completes the proof of Theorem 2.