Geometry Matters in Planar Storyplans

First, there is a time step in which all cycle vertices from a single cycle, say $A$, are visible. Otherwise, consider the time step $e_A$ after which the first cycle vertex of $A$, say $a_1$, disappears, yet $a_3$ has not yet appeared. Then, in $e_A$, the three cycle vertices $a_1,a_2,a_4$ of $A$ and all eight apex vertices must be visible since they need to see both $a_1$ and $a_3$; they induce a non-planar $K_{3,8}$, contradicting that every frame is planar. This holds analogously for the cycles $B,C$. Secondly, there is a time step in which all cycle vertices of all three cycles are visible. Otherwise, consider the time step after which the first cycle vertex disappears. Again, at this time step, we have at least a non-planar $K_{4,8}$ by the same argumentation that the apex vertices need to see both the disappearing cycle vertex and at least one cycle vertex that has not yet appeared.

Now sort the intervals in $I$ by their start points. Consider the first two intervals $[s,e],[s^{\prime },e^{\prime }]$ in this order. Let $q$ and $q^{\prime }$ be their respective apex-vertices. We show that $[s,e]\cap [s^{\prime },e^{\prime }]=\mathrm{\varnothing }$. By our previous arguments, there is a time step $t\in [s,e]$ in which $q$ and all cycle vertices are visible. If $s\le s^{\prime }\le e$, then there is furthermore a time step $t^{\prime }$ with $s^{\prime }\le t^{\prime }\le e$, such that $q$, $q^{\prime }$, and all cycle vertices are visible. Notice that this amounts to $14$ vertices and $36$ edges. Further, the induced drawing of the four-cycles and the two apex-vertices must clearly have a face incident to four vertices – four vertices of one of the four-cycles. Adding a chord, keeping the structure planar, we would end up with $14$ vertices and $37$ edges, a contradiction to Euler’s formula. Symmetrically, by considering the last two intervals when sorted by their end points, we also see that their intersection is empty. The statement follows directly, as each apex must co-occur with each cycle-vertex. $◀$

This follows directly from Lemma 3, as there exists a frame with some apex vertex and all three four-cycles. Clearly, the statement holds, as there is otherwise no face (in the induced drawing of $A$, $B$, and $C$) that contains all four-cycle vertices. $◀$ In the remainder of the proof, we assume that $A$ and $B$ form a non-nested pair.

Next, we want to define one of the drawings of $A$ or $B$ to be “smaller”, see Figure 2. This will be useful in showing that for one of the four-cycles $A$ and $B$, in the drawing of this four-cycle plus an apex-vertex, the other four-cycle will always lie on the outer face.

It is clear that we cannot have $D_1\prec D_2$ and $D_2\prec D_1$. It can, however, be that we have neither. As the drawings of $A$, $B$, and $C$ correspond to simple quadrilaterals, we can show the following lemma (refer to Figure 3 for an illustration). Note that the statement makes sense, as $A$ and $B$ share the outer face.

Assume that $𝒟(A)$ is contained within an inner face of $𝒟(B+q_i^j)$. For the frame $F$, consider the drawing induced by $q_i^j$, $A$, and $B$. Consider the edges on the outer face of this drawing. Two of these connect a vertex of $B$ with $q_i^j$; we denote these vertices as $b$ and $b^{\prime }$. Now, either $A$ is contained within the convex hull of $B$, or the convex hull of $A+B$ contains two line segments $s$ and $s^{\prime }$, each connecting a vertex of $A$ with a vertex of $B$. In the former case, $𝒟(A)\prec 𝒟(B)$ is immediate. In the latter case, $s$ and $s^{\prime }$ are contained within the triangle defined by $b$, $b^{\prime }$, and $q_i^j$. Now notice that, if the intersection point of the lines defined by $s$ and $s^{\prime }$ was closer to $𝒟(B)$ than to $𝒟(A)$, or if $s$ and $s^{\prime }$ were parallel, the points on $s$ and $s^{\prime }$ which are vertices of $B$ would not be visible from $q_i^j$. Hence, we have $𝒟(A)\prec 𝒟(B)$. $◀$ As we cannot have both $𝒟(A)\prec 𝒟(B)$ and $𝒟(B)\prec 𝒟(A)$, we assume, w.l.o.g., that $𝒟(B)\nprec 𝒟(A)$. Thus, in any frame containing $A$, $B$, and some apex vertex $q_i^j$, $B$ will lie on the outer face of the drawing defined by $A$ and $q_i^j$.

We will now show the last ingredient, which can be seen as the key lemma of the construction. Essentially, we want to show that at most two edges of $A$ are “good” – in the sense that they can lie on the outer face of the drawing of $A$ plus some apex vertex (see Figure 4b). More formally, for a fixed drawing of $A$, the edge $e_k^A$, $k\in [4]$, is good if it can be the edge on the outer face of the planar straight-line drawing $𝒟(A+q_i^j)$ for some possible placement of some apex vertex $q_i^j$ in the outer face of $𝒟(A)$. We show the following.

The proof distinguishes two cases, depending on whether $𝒟(A)$ is convex or not. We start with the convex case. We show that it is not possible that $e_1^A$ and $e_3^A$ are both good. By symmetry, this means that $e_2^A$ and $e_4^A$ cannot be both good, and the statement follows. Thus, assume that $e_1^A$ and $e_3^A$ are good. We observe that in the drawing of $A$, each edge defines two open half-planes – the “outer half-plane” and the “inner half-plane” (see Figure 4a for the outer half-planes). More precisely, the outer half-plane defined by $e_i^A$ contains as subset the points which can be connected by straight lines to $a_i$ and $a_{i(mod4)+1}$ without crossings, while the inner half plane does not. Thus, for $k\in [4]$, define $H_k^O$ as the outer half-plane defined by $e_k^A$, and $H_k^I$ as the inner half-plane. As the half-planes are open, they do not contain the line defined by their corresponding edge. Since $e_1$ is good, $H_1^I\cap H_2^O\cap H_3^O\cap H_4^O$ is non-empty (an apex vertex must be able to lie in this region for the drawing to be straight-line planar and for the edge $e_1^A$ to be on the outer face). Similarly, as $e_3$ is good $H_1^O\cap H_2^O\cap H_3^I\cap H_4^O$ is non-empty. Note that $H_2^O\cap H_4^O$ is disjoint from the inner region defined by $𝒟(A)$. For $H_1^O$ and $H_1^I$ to both share points with the intersection of $H_2^O$ and $H_4^O$, the line defined by the drawing of $e_1^A$ must pass through $H_2^O\cap H_4^O$. Because the drawing of $A$ is convex, and because $H_2^O\cap H_4^O$ does not share points with the region defined by $𝒟(A)$, this is not possible. We obtain a contradiction.

For the concave case, w.l.o.g., assume that the concave corner is at $a_2$, with its two incident edges $e_1^A$ and $e_2^A$. We claim that none of $e_1^A$ and $e_2^A$ can be good. For $e_1^A$ to be good, we again have that $H_1^I\cap H_2^O\cap H_3^O\cap H_4^O$ is non-empty. This is not possible: Consider any point $x$ outside $𝒟(A)$ and in $H_1^I$. Notice that the line segment from $x$ to $a_2$ intersects an edge of $A$. Hence, $e_1^A$ cannot be good. The proof that $e_2$ cannot be good proceeds equivalently. $◀$

Assume for a contradiction that $G$ admits a planar geometric storyplan. By our assumption, the drawings of $A$ and $B$ are in each other’s outer face. Further $𝒟(B)\prec 𝒟(A)$ does not hold. Thus, in each of the six frames existing by Corollary 4, $𝒟(B)$ is in the outer face of the drawing induced by $A$ and the apex vertex. For the frame to be planar, the edge vertex of the apex-pair must be on the outer face of the drawing induced by the apex and $A$. Hence, the edge vertex must be connected with a good side of $A$. But, as there are only two good sides (Lemma 8), this is only possible for at most four apex-pairs. Hence, two of the edge vertices of the six apex pairs of Corollary 4 cannot be connected to a good side of $A$, a contradiction. $◀$