The Bend Number of Cocomparability Graphs

By Theorem 4, we have ${𝔇}_k^{=}\subseteq {𝔇}_k^{\le }\subseteq {𝔇}_k^{⊢}$. Now, let $G$ be a graph in ${𝔇}_k^{⊢}$ and let $\mathrm{\Gamma }$ be a ${𝔇}_k^{⊢}$-representation of $G$. Recall that we can assume that $\mathrm{\Gamma }$ is strict. We construct a ${𝔇}_k^{=}$-representation of $G$ from $\mathrm{\Gamma }$ by extending the leftmost segment of each function to $-\mathrm{\infty }$. This new representation ${\mathrm{\Gamma }}^{\prime }$ is clearly a ${𝔇}_k^{=}$-representation, but we need to show that it is a representation of $G$. Clearly, if two functions cross in $\mathrm{\Gamma }$, they still cross in ${\mathrm{\Gamma }}^{\prime }$. Now, let $f,g$ be two functions that do not cross in $\mathrm{\Gamma }$, say $f\le g$. We need to show that $f,g$ still do not cross in ${\mathrm{\Gamma }}^{\prime }$. This is clearly true if the leftmost segment of $f$ has greater or equal slope than $g$, so we may assume this slope is $-1$ while the leftmost segment of $g$ has slope $+1$. Since $k$ is odd and the representation is strict, this means that the rightmost segments of $f$ and $g$ have slopes $+1$ and $-1$ respectively, a contradiction to $f\le g$. $◀$

Our next two results deal with constructions that fail to be representable within a restricted class of curves. They both depend on a geometric counting argument which we now introduce. For a set of points $P$ and an unbounded $k$-bend curve $f$, we say that $f$ cuts off a subset $A\subseteq P$ from $P$, if the points from $A$ are all strictly below the curve $f$, while the points of $P\setminus A$ are strictly above it.

Fix $m$ and fix a point set $P$ of size $N\ge 1$. We say that a set $A\subseteq P$ is small if $|A|\le m$.

Let us proceed by induction on $t$. For $t=0$, the curves under consideration are lines of slopes $+1$ or $-1$ and 1-bend diagonal curves with a single valley. There are at most $m+1$ small subsets of $P$ that can be cut off by a line of slope +1, and likewise at most $m+1$ cut off by lines of slope $-1$. If $A$ is a small set cut off by a diagonal $1$-bend curve with a valley at a point $X$, then $A$ is the union of two sets $A^{+}$ and $A^{-}$ where $A^{+}$ is cut off by the line of slope +1 passing through $X$ and $A^{-}$ by a line of slope $-1$ through $X$. As there are at most $(m+1)$ choices for $A^{+}$ and for $A^{-}$, there are at most ${(m+1)}^2$ such sets $A$.

Suppose now that $t=1$ and consider the curves that have one peak $Y$ and no valleys. Any small set cut off by a curve of this form can be identified in two steps:

1. 1.

   Choose a line $\mathrm{\ell }$ of slope $+1$.

2. 2.

   Choose a point $Y\in \mathrm{\ell }$ so that the 1-bend diagonal curve with a single peak in $Y$ cuts off a small subset of $P$.

In the first step, we can only make $N+1$ combinatorially distinct choices, since we only need to know which points of $P$ are below $\mathrm{\ell }$. In the second step, there are at most $m+1$ distinct small sets that can be cut off once $\mathrm{\ell }$ is fixed. Thus, at most $(m+1)(N+1)$ small sets can be cut off by curves with a single peak and no valleys.

For a curve $f$ with a single peak $Y$ and up to two valleys $X_1,X_2$ with $X_1$ left of $X_2$, the set of points cut off by $f$ is the union of the points cut off by the decreasing line through $X_1$, the points cut off by the 1-bend curve with peak at $Y$, and the points cut off by the increasing line through $X_2$. The number of small sets obtainable in this way is at most ${(m+1)}^3(N+1)$.

For $t\ge 2$, consider a curve $f$ with $t$ peaks, and let $X$ be the valley lying between the first and second peak of $f$. Consider the unbounded diagonal curve $f_1$ whose bends are exactly the bends of $f$ strictly to the left of $X$, and the unbounded diagonal curve $f_2$ whose bends are the bends of $f$ strictly to the right of $X$; in particular, $f_1$ and $f_2$ both pass through $X$, $f_1$ has 1 peak and $f_2$ has $t-1$ peaks. The set of points cut off by $f$ is the union of the set cut off by $f_1$ and the set cut off by $f_2$. By induction, there are at most $c(m,1)c(m,t-1)N^t$ distinct small sets cut off by a curve with $t$ peaks. $◀$

In our applications of Lemma 6, we will assume that $m$ and $t$ are constants, while $|P|$ will grow to $+\mathrm{\infty }$. We then write the bound $c(m,t){|P|}^t$ from the lemma simply as ${𝒪}_{m,t}({|P|}^t)$.

We have ${𝔇}_0^{𝖧}⊊{𝔇}_1^{\nearrow }$, since ${𝔇}_0^{𝖧}$ only contains bipartite permutation graphs, while ${𝔇}_1^{\nearrow }$ is known to be the class of all permutation graphs [22]. Now assume $k\ge 3$, and let $t=\frac{k+1}{2}$.

The separation is witnessed by the graph $G(n)$ consisting of a clique $A$ of size $n$ with a $t$-extension $B$. We easily observe that for any $n$, $G(n)$ has a ${𝔇}_k^{\nearrow }$-representation, see Figure 2.

We will show that for $n$ large enough, $G(n)$ has no ${𝔇}_{k-1}^{𝖧}$-representation. For contradiction, consider a ${𝔇}_{k-1}^{𝖧}$-representation $\mathrm{\Gamma }$ of $G(n)$. For any $a\in A$ and $b\in B$ nonadjacent vertices, the curve $f_a$ is either completely above or completely below $f_b$. Without loss of generality, suppose that $f_a$ is above $f_b$, otherwise we turn $\mathrm{\Gamma }$ upside down. It follows that any other vertex $b^{\prime }\in B$ nonadjacent to $a$ has its representation below $f_a$, because $f_b$ and $f_{b^{\prime }}$ must cross. We conclude that for any pair of nonadjacent vertices $a\in A$ and $b\in B$, the curve $f_a$ is above $f_b$.

Let $P$ be the set of all the endpoints and bends of all the curves of $\mathrm{\Gamma }$ representing vertices in $A$. In particular, $|P|=n(k+2)$, since we may assume that $\mathrm{\Gamma }$ is strict. Every curve representing a vertex from $b$ crosses exactly $t$ curves representing vertices in $A$, and hence it cuts off at most $t(k+2)$ points of $P$. Moreover, two curves representing distinct vertices from $B$ must cut off distinct subsets of $P$. Thus, at least $\left(\genfrac{}{}{0pt}{}{n}{t}\right)$ distinct subsets of $P$ of size at most $(k+2)t$ are cut off in this way. However, the curves of $\mathrm{\Gamma }$ have at most $t-1$ peaks, and therefore can cut off at most ${𝒪}_{k,t}(n^{t-1})$ distinct subsets of $P$ of size at most $t(k+2)$ by Lemma 6. For $n$ large enough, this yields a contradiction. $◀$

For $k=1$ the theorem holds, since ${𝔇}_1^{\nearrow }$ is the class of permutation graphs, while ${𝔇}_1^{=}$ contains the graph $\overline{C_6}$ (the complement of the 6-cycle) which is not a permutation graph (see Figure 3). Suppose that $k\ge 3$ and let $t=\frac{k+1}{2}$.

Let $G(n)$ be the graph consisting of a clique $B$ of size $n$ and two disjoint $t$-extensions $A$ and $C$ of $B$. There are no edges between $A$ and $C$. We easily observe that $G$ has a ${𝔇}_k^{=}$-representation, see Figure 4.

We will show that for $n$ large enough, $G(n)$ has no ${𝔇}_k^{\nearrow }$-representation.

Suppose for contradiction that $G(n)$ has a ${𝔇}_k^{\nearrow }$-representation $\mathrm{\Gamma }$. In $\mathrm{\Gamma }$, for any choice of pairwise nonadjacent vertices $a\in A$, $b\in B$ and $c\in C$, the curve $f_b$ must be between $f_a$ and $f_c$. Suppose without loss of generality that $f_b$ is below $f_a$ and above $f_c$. Since all vertices of $A$ are adjacent to $a$ and all vertices of $C$ are adjacent to $c$, it follows that for any choice of $a^{\prime }\in A$, $b^{\prime }\in B$ and $c^{\prime }\in C$ pairwise nonadjacent, $f_{b^{\prime }}$ is below $f_{a^{\prime }}$ and above $f_{c^{\prime }}$.

Each curve in $\mathrm{\Gamma }$ has $t$ peaks and $t-1$ valleys. Let us turn $\mathrm{\Gamma }$ upside down, and then transform it into a bounded representation by limiting its domain to a bounded interval covering all intersection points and bends. Call the modified representation ${\mathrm{\Gamma }}^{\prime }$. We now repeat the argument of the proof of Theorem 7: let $P$ be the set of bends and endpoints of the curves representing $B$ in ${\mathrm{\Gamma }}^{\prime }$. Each curve representing a vertex $a\in A$ in ${\mathrm{\Gamma }}^{\prime }$ has at most $t-1$ peaks, and cuts off from $P$ a subset of size at most $t(k+2)$. By Lemma 6, there are at most ${𝒪}_k(n^{t-1})$ such subsets of $P$, whereas $A$ has $\left(\genfrac{}{}{0pt}{}{n}{t}\right)$ vertices, and each must correspond to a different set being cut off. For $n$ large enough, this yields a contradiction. $◀$

We complete the case of $k$ odd by a result for odd and even numbers of bends.

Fix $G\in {𝔇}_k^{=}\setminus {𝔇}_k^{\nearrow }$. It follows that $G$ is also in ${𝔇}_k^{𝖧}$, and we easily see that ${𝔇}_k^{𝖧}$ is closed under disjoint unions, hence $G+G\in {𝔇}_k^{𝖧}$. For contradiction, assume that $G+G$ has a ${𝔇}_k^{⊢}$-representation $\mathrm{\Gamma }$. If every component of $G$ is in ${𝔇}_k^{\nearrow }$, then $G$ itself is in ${𝔇}_k^{\nearrow }$, a contradiction. Hence, $G$ has a connected component $C$ not belonging to ${𝔇}_k^{\nearrow }$.

Let $C_1$ and $C_2$ be two components isomorphic to $C$ inside $G+G$. In $\mathrm{\Gamma }$, the representations of $C_1$ and $C_2$ must include curves with increasing unbounded segments as well as those with decreasing unbounded segments, otherwise $C$ would have a ${𝔇}_k^{\nearrow }$-representation. Since each copy of $C$ is connected, the left endpoints of its curves must appear consecutively on the grounding line of $\mathrm{\Gamma }$. It follows that in $\mathrm{\Gamma }$, a curve from the representation of $C_1$ crosses a curve from the representation of $C_2$, which is impossible. $◀$

Since $A,C$ and $E$ are disjoint cliques, all functions in one of them lie above or below all functions of another. If $C$ is not in the middle, then $A$ is in the middle without loss of generality. However, this is impossible, because the functions of $D$ are supposed to intersect functions of $C$ and $E$ while not intersecting any from $A$. Thus, $C$ is in the middle. If $A$ were below $C$ and $E$ above it, we could simply relabel the vertices, since $H_t(n)$ admits an automorphism that exchanges $A$ with $E$ and $B$ with $D$. $\mathrm{⊲}$

Pick an arbitrary $𝔇$-representation $\mathrm{\Gamma }$ of $H_t(2n-1)$, with central clique $C$. Clearly $C$ contains a subset of $n$ curves whose leftmost segments are parallel. By restricting to this subset, we enforce the property.

If $C$ does not contain $n$ upwards-starting curves, then it contains a set $C^{\prime \prime }$ of $n$ downwards starting curves. We restrict $\mathrm{\Gamma }$ by this set $C^{\prime \prime }$, and turn the resulting representation upside down. To ensure that Property 1 is preserved, we again relabel vertices according to the automorphism that maps $A$ to $E$ and $B$ to $D$. $\mathrm{⊲}$

We may in fact assume without loss of generality that in the representations satisfying Property 2 the leftmost segments in the curves representing $C$ are all increasing. This is automatic when $𝔇={𝔇}_b^{\nearrow }$, and for $𝔇\in \{{𝔇}_{,}^{=}{𝔇}_{,}^{⊢}{𝔇}_{\}}^{𝖧}$, this can be achieved by turning the representation upside down and relabeling vertices to ensure Property 1 also holds. From now on, we will restrict ourselves to representations where the leftmost segments of the curves representing the central clique are all increasing.

Note that all curves in $C$ have exactly $b$ bends. Since they start upwards, they have exactly $\lceil \frac{b}{2}\rceil$ peaks and $\lfloor \frac{b}{2}\rfloor$ valleys. We will say that a point $(x,y)\in ℝ$ lies above another point $(x^{\prime },y^{\prime })$, if $y-y^{\prime }>|x-x^{\prime }|$. A set of points is independent, if no point of the set lies above any other. Note that since all functions in the diagonal representation are Lipschitz-continuous with Lipschitz constant 1, if a point on the curve $f$ lies above a point on the curve $g$, then $f\ge g$ on the interval in between those two points.

From now on, we will scale our $𝔇$-representations in such a way, that the $x$-coordinate every bend and every intersection point is in the interval $(0,1)$. Furthermore, the domain of a bounded representation is taken to be $[0,1]$ and the domain of a grounded representation is $[0,+\mathrm{\infty })$.

Start with a representation of $H_t(n+2t)$ satisfying the previously enforced properties. Choose $d\in D$ so that $f_d(0)$ is maximised. Note that if there is a $c\in C$ such that , then $f_d$ crosses $f_c$. This is because $d$ is adjacent to a vertex $e\in E$, and by Property 1. Since $d$ has $t$ neighbors in $C$, there can be at most $t$ vertices $c\in C$ for which . By deleting these at most $t$ vertices, we enforce that for every $c\in C$ and $d\in D$, $f_c(0)$ is greater than $f_d(0)$. By a similar argument, we also enforce that $f_c(1)>f_d(1)$, after deleting another set of at most $t$ vertices. $\mathrm{⊲}$

Note that Property 3 implies that for any $c\in C$ and $d\in D$, $f_c$ and $f_d$ intersect an even number of times. Moreover, if $P$ and $Q$ are two consecutive intersections of $f_c$ and $f_d$ so that $f_d$ stays above $f_c$ between $P$ and $Q$, then $f_d$ has at least one peak and $f_c$ at least one valley between $P$ and $Q$, and the leftmost such peak of $f_d$ lies above the leftmost such valley of $f_c$.

From this point on, we will denote some of the valleys of the functions representing $C$ as active. To determine which valleys are active, we first consider all of them as active, that is $\lfloor \frac{b}{2}\rfloor$ per function, then do $\lfloor \frac{b}{2}\rfloor$ steps: In step $i$, we consider all functions with exactly $\lfloor \frac{b}{2}\rfloor -i+1$ active valleys. As long as an active valley $v_1$ of such a function $f_1$ representing $c_1\in C$ lies above an active valley of such a function $f_2$ representing $c_2\in C$, we delete $c_2$ from $C$ and deactivate $v_1$. This procedure deletes at most half of the elements of $C$ in each step, so at least $\frac{N}{2^{\lfloor \frac{b}{2}\rfloor }}\ge n$ elements remain. The procedure enforces the following two properties.

Assume for a contradiction that some function $f_d$ obeys $f_d(x)>f_c(x)$, where $(x,y)$ is a valley of $f_c$ that is not active. Since all valleys were active before the procedure, there was a certain step in which $(x,y)$ was deactivated. In this step another function $f_{c^{\prime }}$ was deleted, whose valley $(x^{\prime },y^{\prime })$ obeys $y-y^{\prime }>|x-x^{\prime }|$. Since $f_d$ is Lipschitz continuous with Lipschitz constant 1, we get

Since , by continuity $f_d$ crosses $f_{c^{\prime }}$ and should have therefore been removed when $c^{\prime }$ and all of its neighbors were removed, a contradiction. $\mathrm{⊲}$

This is true after step $\lfloor \frac{b}{2}\rfloor -i+1$ because it would not have ended otherwise. It stays true as the functions with $i$ active valleys are not changed in any of the further steps. $\mathrm{⊲}$

Let $0\le m\le \lfloor \frac{b}{2}\rfloor$ be a number that maximizes the number of functions of $C$ with exactly $m$ active valleys. At least $\frac{N}{\lfloor \frac{b}{2}\rfloor +1}\ge n$ elements of $C$ are represented by such functions by the pigeon-hole principle. Then delete all other elements of $C$. $\mathrm{⊲}$ From Properties 5 and 6 we can now deduce that all active valleys of functions representing $C$ are independent. By Property 4, only active valleys can be used for intersection with functions representing $D$.

Since the active valleys are independent, they form a natural left-to-right sequence. It is convenient to view such a sequence as a word over the alphabet whose symbols are the vertices in the central clique $C$. We first introduce some related terminology.

We will say that a word $w$ is $m$-regular over an alphabet $X$, if it contains exactly $m$ occurrences of each symbol from $X$, and no other symbols. We say that a word $w$ is an $m$-immediate repetition over an alphabet $X$ if it has the form $w=x_1^m{x}_2^m\mathrm{\cdots }{x}_n^m$, where $x^m$ denotes an $m$-fold repetition of the symbol $x\in X$, and the $n$-tuple $(x_1,\mathrm{\dots },x_n)$ is a permutation of the alphabet $X$.

We will now introduce the pattern of the active valleys, which is a word $w$ over the alphabet $C$ whose $i$-th symbol $w_i$ is the vertex whose curve contains the $i$-th active valley from the left. Note that $w$ is $m$-regular over $C$, by Property 6.

Set $N=m{n}^2$, and let $w$ be an $m$-regular word over $[N]$. To each symbol $x\in [N]$ we associate the interval $I_x=[x^i,x^j]$ where $x^i,x^j$ are the indices of the first and last occurrence of $x$ in $w$.

We then construct an interval graph $G(w)$ as the graph on the vertex set $[N]$ where distinct vertices $x,y\in [N]$ are adjacent if and only if the intervals $I_x$ and $I_y$ intersect. This graph is an interval graph and therefore perfect. In particular, it satisfies $\alpha (G(w))\cdot \omega (G(w))\ge N$, where $\alpha (G(w))$ and $\omega (G(w))$ denote the size of the largest independent set and the largest clique of $G(w)$, respectively.

We thus have $\alpha (G(w))\ge n$ or $\omega (G(w))\ge mn$. If the former is true, we let $C$ be an independent set of size $n$ in $G(w)$, and we see that Case $2$ of the lemma occurs.

On the other hand, if $\omega (G(w))\ge mn$, we first fix a clique $Q$ of size $mn$ in $G(w)$. The intervals representing the vertices of $Q$ have nonempty intersection by Helly’s theorem, and since all these intervals have distinct endpoints by construction, their common intersection is a non-degenerate interval $J$. Choose a $p\in J$ such that $p+1$ is also in $J$. Let us call the prefix $w_1{w}_2\mathrm{\cdots }{w}_p$ the left part of $w$, and the suffix $w_{p+1}\mathrm{\cdots }{w}_N$ the right part of $w$. Each symbol $x\in Q$ thus appears both in the left part and in the right part.

For $j\in [m-1]$, let $Q_j$ be the set of those symbols $x\in Q$ that have exactly $j$ occurrences in the left part. Choose the value of $j$ for which the size of $Q_j$ is maximised, and set $C=Q_j$. We then have $|C|\ge |Q|/(m-1)\ge n$, and the restriction of $w$ to the symbols of $C$ satisfies Case 1 of the lemma. $◀$

Apply Lemma 10 iteratively to the intervals in the first case, until the second case is encountered (which is definitely the case if $m=1$). Note that removing letters from the alphabet of the pattern is equivalent to deleting elements of $C$. $\mathrm{⊲}$ We may assume that the order of valleys in the first interval $I_1$ is $(1,\mathrm{\dots },n)$ by relabeling the vertices in $C$ if necessary.

For this step choose $N=n^{2^{\mathrm{\ell }-1}}$. For each interval consider the sequence of letters of the alphabet, ordered by their occurrences in the interval. In each interval choose one representative of each letter to have a permutation of $(1,\mathrm{\dots },n)$ as subsequence. We consider just those permutations. By the Erdős-Szekeres Lemma [11], each sequence of $n^2$ numbers contains a subsequence of $n$ numbers that is either monotonically increasing or monotonically decreasing. With the assumption that the sequence for $I_1$ is $(1,\mathrm{\dots },N)$, it is possible to find a subset of $\sqrt{N}$ letters such the permutation for $I_2$ is increasing or decreasing. By removing all letters not in the subset and repeating the process for each of the intervals $I_3,\mathrm{\dots },I_{\mathrm{\ell }}$, we end up with at least $N^{\frac{1}{2^{\mathrm{\ell }-1}}}=n$ letters such that each interval contains the subsequence $(1,\mathrm{\dots },n)$ or $(n,\mathrm{\dots },1)$ after relabeling. $\mathrm{⊲}$

For a set of $t$ vertices from $C$, we let $d_I\in D$ denote the vertex in $D$ adjacent to the vertices in $I$. For such $I$ we further define the crossing type of $I$ as the $t$-tuple $(i(1),i(2),\mathrm{\dots },i(t))\in {[\mathrm{\ell }]}^t$ such that for every $j\in [t]$, the curve of $d_I$ has a peak above a valley of the curve of $c_j$ which occurs in the interval $I_{i(j)}$. The crossing type need not be determined uniquely, in which case we assign one fixed crossing type to each $I\in \left(\genfrac{}{}{0pt}{}{C}{t}\right)$ arbitrarily.

The crossing types define a coloring of the set $\left(\genfrac{}{}{0pt}{}{C}{t}\right)$, and we apply Ramsey’s Theorem to this coloring. $\mathrm{⊲}$

Since all valleys are independent, every peak lies above a consecutive set of valleys. Say a peak $p$ of $d_I$ lies above valleys of vertices $i$ and $j>i+1$ from $C$. If these valleys are in the same interval, Property 8 makes sure that a valley of the function of $i+1$ lies in between those two valleys, a contradiction since $i+1\notin I$. If the valleys of $i$ and $j$ are in different intervals, then the end of one interval and the beginning of the other are contained in $I$, which is impossible, since $I$ contains neither 1 nor $n$. $◀$

We already noted that $H_t(n)$ has a ${𝔇}_k^{\nearrow }$-representation for any $n$. For contradiction, assume that $H_t(n)$ also has a ${𝔇}_{k-1}^{𝖧}$-representation for $n$ arbitrarily large.

It follows that for arbitrarily large $n$, the graph $H_t(n)$ has a ${𝔇}_{k-1}^{𝖧}$-representation with all the properties listed above. We say that a peak $p$ of a function representing $d\in D$ collects an element $c\in C$ if it lies above one of the valleys of $f_c$. Consider the $t$-subset $I=\{i_1,\mathrm{\dots },i_t\}\subseteq C,0\le i_1-4\le i_2-8\le \mathrm{\dots }\le i_t-4t$. Since $I$ does not contain two consecutive integers, nor both $n$ and $1$, every peak of $f_{d_I}$ collects a different element of $I$ by Lemma 11. Let $(r_1,\mathrm{\dots },r_t)\in C^t$ be the order of the elements of $I$ given by the order of $x$-coordinates of the peaks of $f_{d_I}$ that collect them. By Property 8 for each $i\in [\mathrm{\ell }]$, we can set

We will proceed to show that $\forall x\in [0,1]:f_{d_I}(x)>{\min }_{i\in \{L,R\}}{f}_{d_{I_i}}(x)$ which is a contradiction since $E$ contains an element that is adjacent to $d_I$ but neither $d_{I_L}$ nor $d_{I_R}$.

To see this, first note that neither of $I_L$ and $I_R$ contain a pair of consecutive numbers, nor do they contain $n$ and further their elements $r_i\pm 1$ are in the same order as the $r_i$, since $|r_i-r_j|\ge 4\forall i\ne j\in [t]$. Therefore $r_i\pm 1$ is in the same interval as $r_i$ by Property 9. The peak of $f_{d_I}$ collecting $r_i$ is therefore always in between the peaks of $f_{d_{I_L}}$ and $f_{d_{I_R}}$ collecting $r_i\pm {\sigma }_{c_{r_i}}$. Therefore $f_{d_{I_L}}$ is below $f_{d_I}$ between the peaks collecting $r_i$ and $r_{i+1}$ if $i$ is even, because in this case the valley of $r_i-{\sigma }_{c_{r_i}}{(-1)}^i$ is to the left of the valley of $r_i$ and the valley of $r_{i+1}-{\sigma }_{c_{r_{i+1}}}{(-1)}^{i+1}$ is to the right of the valley of $r_{i+1}$. The argumentation is the same for $f_{d_{I_R}}$ if $i$ is odd. Finally the first segment of $f_{d_I}$ is above the function $f_{d_{I_L}}$ because the valley where $r_1+{\sigma }_{c_{r_1}}$ is collected is the right neighbor of the valley of $r_1$. Therefore the function of $d_I$ is lower than either of the functions representing $d_{I_R}$ and $d_{I_L}$ at any point, which completes the contradiction. $◀$

For our next theorem, we exploit the properties of the $𝔇$-representations of $H_t(n)$ in a different way.

Recall that our proof of Theorem 12 has in fact shown that in a representation of $H_t(n)$, there will be a vertex $v_I\in D$ and two other vertices $v_{I_L}$ and $v_{I_R}$ with the property that each of the $t$ peaks of the curve of $v_I$ is needed to collect a distinct valley of a curve from $C$, while each of the $t-1$ valleys of $v_I$ between these $t$ peaks is above a valley of $v_{I_L}$ or $v_{I_R}$. In this situation, we say that $v_I$ is protected by $v_{I_L}$ and $v_{I_R}$. In a ${𝔇}_{k-1}^{𝖧}$-representation, such a protected vertex yielded a contradiction, since it could not have been crossed by any of its neighbors in $E$. In a ${𝔇}_k^{\nearrow }$-representation, this merely means that any $E$-neighbor of a protected vertex must collect its rightmost valley.

Suppose that we have chosen $n$ large enough to be able to construct $2t+1$ protected vertices $w_1,w_2,\mathrm{\dots },w_{2t+1}$ in $D$, and let $q_i$ be the rightmost valley in the representation of $w_i$. Note that the points $q_1,\mathrm{\dots },q_{2t+1}$ must be independent, since for each of them, there is a neighbor in $E$ that must collect it while avoiding all the others. Suppose that $q_1,\mathrm{\dots },q_{2t+1}$ were numbered left-to-right (see Figure 8). Consider now a vertex $u$ of $E$ adjacent to $w_2,w_4,\mathrm{\dots },w_{2t}$. Each peak in the representation of $u$ must collect a different valley among $q_2,\mathrm{\dots },q_{2t}$, since a single peak collecting more than one of these points would also collect an odd-numbered valley between them.

Let $\mathrm{\ell }$ now be a line of slope $+1$ chosen directly above the leftmost segment of $u$, so that the valley $q_1$ is above it. It follows that $f_u$ is below $\mathrm{\ell }$, while the entire representation of $w_1$ is above it, since $q_1$ is the rightmost bend of the representation of $w_1$. $◀$

Let $G\in {𝔇}_k^{=}$. Then the functions where the leftmost segment goes upward induce a graph $G_1\in {𝔇}_k^{\nearrow }$ and the functions where the leftmost segment goes downward induce a graph $G_2\in {𝔇}_k^{\nearrow }$ (where the representation is obtained by mirroring at a horizontal line). Note that each function for $G_1$ crosses each function for $G_2$ since $k$ is even. Conversely, given $G_1,G_2\in {𝔇}_k^{\nearrow }$ we obtain the representation of the corresponding graph $G$ by combining the representation of $G_1$ and the mirrored representation of $G_2$ (after adding bends such that each function has $k$ bends). $◀$

We will show that the conclusion of the theorem holds for the graph $G$ which is the join of two copies of $H_t(n)$, with $t=\frac{k}{2}$. Since we already know that $H_t(n)$ is in ${𝔇}_k^{\nearrow }$ by Theorem 12, Lemma 14 shows that $G$ is in ${𝔇}_k^{=}$. We now prove that $G$ is not in ${𝔇}_k^{\nearrow }$.

Suppose that we are given a ${𝔇}_k^{\nearrow }$-representation $\mathrm{\Phi }$ of $G$. Let $G_1$ and $G_2$ denote the two copies of $H_t(n)$ whose join is $G$. By Lemma 13, for each $G_i$ there is a line ${\mathrm{\ell }}_i$ of slope $+1$ such that in $\mathrm{\Phi }$ there are curves representing vertices of $G_i$ both fully above and fully below ${\mathrm{\ell }}_i$. Suppose without loss of generality that ${\mathrm{\ell }}_1$ is above ${\mathrm{\ell }}_2$. Then $G_1$ has a vertex $v_1$ represented by a curve $f_1$ above ${\mathrm{\ell }}_1$, and $G_2$ has a vertex $v_2$ represented by a curve $f_2$ below ${\mathrm{\ell }}_2$. In particular, $f_1$ and $f_2$ are disjoint, contradicting the fact that $v_1$ and $v_2$ are adjacent in $G$. $◀$

Fix a graph $G\in {𝔇}_k^{=}\setminus {𝔇}_k^{\nearrow }$. Since $G\notin {𝔇}_k^{\nearrow }$, any ${𝔇}_k^{=}$-representation $\mathrm{\Gamma }$ of $G$ contains at least one function $f_{\mathrm{\Gamma }}$ whose leftmost segment has slope $+1$ and at least one function $g_{\mathrm{\Gamma }}$, whose leftmost segment has slope $-1$. Since $k$ is even, any function starting with an increasing segment must cross any function starting with a decreasing one, in particular $G$ is connected.

To prove the first part of the theorem, assume that $G+K_1$ can be represented in ${𝔇}_k^{=}$ and fix one such representation $\mathrm{\Phi }$. Let ${\mathrm{\Gamma }}^{\prime }\subset \mathrm{\Phi }$ be the set of functions in $\mathrm{\Phi }$ corresponding to $G$ and let $h$ be the function in $\mathrm{\Phi }$ representing the single vertex in $K_1$. Then, without loss of generality, the leftmost segment of $h$ has slope $-1$ and therefore $h$ crosses $f_{{\mathrm{\Gamma }}^{\prime }}$, contradicting the assumption that $\mathrm{\Phi }$ is a representation of $G+K_1$. On the other hand, we can obtain a ${𝔇}_k^{\le }$-representation of $G+K_1$ by placing a function consisting of two pieces with slopes $-1$ and $+1$ very far above ${\mathrm{\Gamma }}^{\prime }$.

The second part of the theorem is already covered by Theorem 9.

To prove the last part of the theorem, we assume that $H$ can be represented in ${𝔇}_k^{\le }$ with a representation $\mathrm{\Phi }$. Then, let $f\in \mathrm{\Phi }$ be a function representing a vertex in $G_1^{\prime }$, we can assume that the leftmost segment of $f$ has slope $+1$. Further, by our choice of $G$ and $H$, there is at least one other function $g\in \mathrm{\Phi }$, representing a vertex of either $G_1^{\prime \prime }$ or $G_2^{\prime \prime }$ which has leftmost segment with slope $-1$. Since $k$ is even, $f$ and $g$ cross each other. But this is impossible since vertices in $G_1^{\prime }$ are not adjacent to any vertices in $G_1^{\prime \prime }$ nor to any vertices in $G_2^{\prime \prime }$, so $\mathrm{\Phi }$ cannot be a representation of $H$. On the other hand, in Figure 9 we explain how to obtain a ${𝔇}_k^{⊢}$-representation of $H$. $◀$