Proof. Here, we show that for any positive integer \(i\), \({\mathcal{C}}^{i} \subseteq {\mathcal{C}}^{i+1}\). Let \(G = (U \cup V, E) \in {\mathcal{C}}^i\). Then take \(H\) being the complete bipartite graph on \(U\) and \(V\) (where the edges connect vertices in \(U\) and \(V\)). Then \(H \in {\mathcal{C}}\). Therefore, \(G = G\cap H \in {\mathcal{C}}^{i+1}\). ◻

Proof. Let \(H\) be a chordal bipartite graph. If for every induced subgraph of \(H\), a node of degree at most \(k-1\) exists, we are done. Therefore, let us assume by contradiction that \(G\) is an induced subgraph of \(H\), where a node of degree at most \(k-1\) does not exist. Then all nodes \(V(G)\) have a degree of at least \(k\) in \(G\). Using 2, we know that there is a \(P\)-free biadjacency matrix of \(G\), where \(P=\begin{psmallmatrix} 0 & 1 \\ 1 & 1 \end{psmallmatrix}\). Let \(M_G\) be that biadjacency matrix. Let \(G = (U \cup V, E)\), where each row \(i \in [|U|]\) and column \(j \in [|V|]\) correspond to the vertices \(u_i \in U\) and \(v_j \in V\), respectively. Let \(i \in [|U|]\) be the maximum integer, such that \(M_G(i, |V|) = 1\) (i.e., this is the bottommost row in the last column such that the entry is one). Consider the rows \(R= \{i': u_{i'} \in N_G(v_{|V|})\}\subseteq [|U|]\) and columns \(C= \{j': v_{j'} \in N_G(u_i)\}\subseteq [|V|]\).

Let \(M'\) be the submatrix induced on rows \(R\) and columns \(C\). According to our assumption, this submatrix \(M'\) contains at least \(k\) rows and \(k\) columns. It is easy to see that \(M'\) is an all-one matrix: Assume that it is not, and \(M_G(a,b) = 0\) for some \(a \in R\) and \(b \in C\). Since \(a \in R\), we have \(M_G(a,|V|) = 1\) and since \(b \in C\), \(M_G(i,b)=1\). The \(2\)-by-\(2\) submatrix induced on rows \(\{a,i\}\) and columns \(\{b,|V|\}\) is then equal to the forbidden pattern \(P\), a contradiction. ◻

Proof. The result follows from 1 and [obs:32degenrate32counting]. ◻

Proof. The result follows from 3 when \(n = m\). ◻

Proof. Let \(H\) be a segment-ray graph. If, for every induced subgraph of \(H\), a node of degree at most \(2(k-1)\) exists, we are done. Therefore, let us assume by contradiction, that \(G\) is an induced subgraph of \(H\), where a node of degree at most \(2(k-1)\) does not exist. Then, all nodes \(V(G)\) must have a degree at least \(2k -1\) in \(G\).

Let \(({\mathcal{S}}, {\mathcal{R}}, \phi)\) be the \(\mathop{\mathrm{\sf{ SR}}}\) representation of \(G = (U \cup V, E)\), such that \(\phi: U \mapsto {\mathcal{S}}, V \mapsto {\mathcal{R}}\). Let \(x\) and \(y\) be the horizontal and vertical axes, respectively. Each ray \(r\in{\mathcal{R}}\) can be addressed by a pair \((r_x,r_y)\), where \(r_x\) and \(r_y\) are the \(\boldsymbol{x}\) and \(\boldsymbol{y}\) coordinates of its starting point respectively. Each horizontal segment \(s\in{\mathcal{S}}\) can be addressed using three variables \((s_l, s_r, s_y)\), such that \([s_l, s_r]\) and \(s_y\) are the projections of \(s\) to the \(x\) and \(y\) axis respectively.

Let \(r \in {\mathcal{R}}\) be the ray with the largest \(r_y\) (highest starting point). Let \(S\) be the set of segments that intersect \(r\). Then, according to our assumption, \(|S|\geq 2k-1\). Let \(S_{right} \subseteq S\) be the set of \(k-1\) segments with the largest (rightmost) \(s_r\), and let \(S_{left} \subset S\) be the set of \(k-1\) segments with the least (leftmost) \(s_l\). Then there must be at least one segment \(s \in S \setminus (S_{right} \cup S_{left})\) (3).

Let \(R\) be the set of rays that intersect \(s\). By our assumption, \(|R| \geq 2k-1\). Let \(R_{left}, R_{right} \subseteq R\) be the sets of rays to the left and right of \(r\), respectively. Since \(R = R_{left} \cup R_{right} \cup \{r\}\), then at least one of \(R_{left}, R_{right}\) must contain at least \(k-1\) rays. Let us assume it is \(R_{left}\), the other case can be argued symmetrically. Since \(r\) is the ray with the highest \(r_y\), then each ray in \(R_{left}\) must intersect each segment in \(S_{left}\) (3). This implies that the vertices mapped to rays in \(R_{left} \cup \{r\}\) and segments in \(S_{left} \cup \{s\}\) must induce a \(k\)-by-\(k\) biclique. This is a contradiction. ◻

Proof. The result follows from 2 and [obs:32degenrate32counting]. ◻

Proof. We present the proof for DL-bulky edges. The proofs for the other two cases are similar. Let \(B \subseteq N_G(u)\) be the nodes \(v \in V\), such that \(\{u, v\}\) is DL-bulky. Let \(S' \subseteq \mathop{\mathrm{\sf{ succ}}}^{DL}(\phi(u))\) be the \(k-1\) segments \(s' \in S'\) with the largest \(\min(s'.x)\). Let \(U'\) be the set of nodes represented by \(S'\).

We will show that each \(v \in B\) has \(\{u\} \cup U'\) in its neighborhood, and therefore \(|B| \leq k-1\). Assume by contraposition that \(|B| \geq k\). Let \(v\in B\) be an arbitrary node. For any \(s'\in S'\), \(\phi(u) \prec_{DL} s'\) and \(\phi(u) \subseteq \phi(v)\) imply the following:

• \(s'.y \in \phi(v).y\). Since \(\phi(u) \prec_{DL} s'\), we have \(s'.y\leq \phi(u).y\), and since \(\phi(v)\) contains \(\phi(u)\), we have \(\phi(u).y \in \phi(v).y\). Since \(\phi(v).y\) is an interval that starts at \(- \infty\), then \(s'.y \in \phi(v).y\).

• \(\max(s'.x) \leq \max(\phi(v).x)\). Similarly to the previous case, the implications give us the inequalities in \(\max(s'.x) \leq \max(\phi(u).x) \leq \max(\phi(v).x)\)

Let \(s' \in S'\) be an arbitrary segment. Since \(\phi(v).y\) contains \(s'\) on the \(y\)-axis, \(\max(\phi(v).x)\) is larger than any point in \(s'\) on the \(x\)-axis, then to show that \(\phi(v)\) contains \(s'\), it only remains to show that \(\min(\phi(v).x) \leq \min(s'.x)\). Since \(S'\) was chosen to contain the segments in \(\mathop{\mathrm{\sf{ succ}}}^{DL}(\phi(u))\) with the largest \(\min(s'.x)\), then \(\min(\phi(v).x) \leq \min(s'.x)\) holds for \(s' \in S'\), if it holds for any \(k-1\) segments in \(\mathop{\mathrm{\sf{ succ}}}^{DL}(\phi(u))\). Since \(\{u, v\}\) is DL-bulky, \(\phi(v)\) contains at least \(k-1\) segments in \(\mathop{\mathrm{\sf{ succ}}}^{DL}(\phi(u))\). This implies that \(\phi(v)\) contains \(S'\), and we have \(U' \in N_G(v)\). Since this is true for all \(v \in B\), then \(B\) and \(U'\cup\{u\}\) induce a \(K_{k,k}\), which is a contradiction.

The proof for DR-bulky edges is symmetric and the proof for C-bulky edges can easily be seen by selecting \(S' \subseteq \mathop{\mathrm{\sf{ succ}}}^{C}(\phi(u))\) to be the \(k-1\) segments \(s' \in S'\) with the smallest \(s'.y\). Since every \(s' \in S'\) is already contained in \(\phi(u)\) on the \(x\)-axis, then the \(y\) coordinate is the only factor determining which elements of \(\mathop{\mathrm{\sf{ succ}}}^{C}(\phi(u))\) are contained within a bottomless rectangle that contains \(\phi(u)\). ◻

Proof. For a partial order \({\mathcal{P}}\), we use \(E({\mathcal{P}})\) to denote the number of comparable pairs in \({\mathcal{P}}\).

Let \(T\subset N_G(v)\) be the set of nodes \(u\), such that \(\{u,v\}\) is thin. Let \({\mathcal{P}}_l, {\mathcal{P}}_r, {\mathcal{P}}_c\) be the partial orders \({\mathcal{P}}^{DL}, {\mathcal{P}}^{DR}, {\mathcal{P}}^C\) induced on set \(\phi(T)\). According to [lem:chain395all95ordered], each pair of segments \(s, s' \in \phi(T)\), is comparable in at least one of the partial orders. We then have \(|E({\mathcal{P}}_l) \cup E({\mathcal{P}}_r) \cup E({\mathcal{P}}_c)| \geq {|T| \choose 2}\).

Since for all \(u \in T\), the edge \(\{u,v\}\) is thin, there are at most \((k-2)\) DL-successors of \(\phi(u)\) in \(\phi(T)\), so we have \(|E({\mathcal{P}}_l)| \leq (k-2)|T|\). Similarly, we have at most \((k-2)\) C-successors and \((k-2)\) DR-successors in \(\phi(T)\). Therefore, \(|E({\mathcal{P}}_r)|, |E({\mathcal{P}}_c)| \leq (k-2)|T|\). Combining the edges in the three partial orders, we get \(|E({\mathcal{P}}_l) \cup E({\mathcal{P}}_r) \cup E({\mathcal{P}}_c)|\leq 3(k-2)|T|\). Putting these inequalities together, we have \[|T|(|T|-1)/2 = {|T| \choose 2} \leq 3(k-2)|T|\] which implies that \(|T| \leq 6k-11<6(k-1).\) ◻

Proof. Let \(G = (U \cup V, E) \in \mathop{\mathrm{\sf{ CHAIN}}}^3\) be a \(K_{k, k}\)-free graph, where \(|U| = m\), \(|V| = n\). Note that we defined every edge in \(E\) as either thin or bulky. According to 4, the number of bulky edges in \(E\) is at most \(3(k-1) m\). According to 5, the number of thin edges in \(E\) is at most \(6(k-1) n\). This means that the total number of edges is \(|E| \leq (3m+6n)(k-1)\). ◻

Proof. The first part will be proved in 4. The second part is a simple corollary of existing results: Chazelle [31] constructed \(K_{2,2}\)-free \(\mathop{\mathrm{\sf{ PRIG}}}\) graphs on \(n'\) vertices that have at least \(\Omega(n' \cdot \frac{\log n'}{\log \log n'})\) edges. Chan and Har-Peled [3] assert the applicability of this result in graph theory, since the original context was pointer machines. By a simple modification that we show in 17, there exist \(K_{k,k}\)-free \(\mathop{\mathrm{\sf{ PRIG}}}\) graphs on \(N\) vertices with at least \(\Omega(N\cdot (k-1) \cdot \frac{\log \frac{N}{k-1}}{\log \log \frac{N}{k-1}}) = \Omega(N\cdot k \cdot \frac{\log N}{\log \log N})\) edges. Since \(\mathop{\mathrm{\sf{ PRIG}}}\subseteq \mathop{\mathrm{\sf{ CONV}}}^2\) (13), which is contained in \(\mathop{\mathrm{\sf{ CHAIN}}}^4\) [6], then the constructed graphs give a lower bound for Zarankiewicz numbers for \(\mathop{\mathrm{\sf{ CHAIN}}}^4\) graphs. ◻

Proof. We choose the maximum number \(\ell\) of disjoint sets \(S_1, \ldots S_{\ell}\) in \(N(\nu)\), such that every set \(S_i\) satisfies the conditions of 6. Since each set receives \(\frac{9}{2} (k-1)\) credits from a distinct set of horizontal segments, then the total amount in credits \(\nu\) receives is at least \(\frac{9}{2} (k-1) \ell\). It remains to see that \(\frac{9}{2} (k-1) \ell \geq |N(\nu)|\). Note that \(\ell \geq \lfloor \frac{|N(\nu)| - 3(k-1) - 3(k-1)}{3(k-1)}\rfloor \geq \frac{|N(\nu)| - 9(k-1)}{3(k-1)}\). We get that \(\frac{9}{2} (k-1) \ell \geq \frac{9}{2} (k-1) \frac{|N(\nu)| - 9(k-1)}{3(k-1)} = \frac{3}{2}|N(\nu)| - \frac{27}{2}(k-1) = |N(\nu)| + \frac{1}{2}(|N(\nu)| - 27(k-1))\). Since according to our assumption \(|N(\nu)| \geq 27(k-1)\), then this result is at least \(|N(\nu)|\). ◻

Proof. Assume by contradiction that there is a graph \(G = (U \cup V, E) \in \mathop{\mathrm{\sf{ GIG}}}\), where no such node exists. Since according to our assumption, for any node \(w \in U \cup V\), we have \(|N(w)| \geq 27(k-1) + 1\), then by running 7 and 8, we see that for each horizontal node, fewer credits are given out than their degree. This implies that the amount in credits given by these algorithms is smaller than \(|E|\).

For each vertical node \(\nu\in \mathbf{Y}\), on the other hand, according to 7, the amount in credits received is at least that of their degree. This implies that the total amount in credits received from these algorithms greater than or equal to \(|E|\). This is a contradiction. ◻

Proof. The result follows from 8 and [obs:32degenrate32counting]. ◻

Proof. The result follows from 6, when \(n = m\) ◻

Proof. The proof is obtained by induction on \(d\). The base case when \(d = 3\) is proved in 5. When \(d > 3\), assume the claim is true for all dimensions up to \(d-1\). We write \(G = G' \cap \widehat{G}\) where \(G' \in \mathop{\mathrm{\sf{ CHAIN}}}\) and \(\widehat{G} \in \mathop{\mathrm{\sf{ CHAIN}}}^{d-1}\). Since \(G' \in \mathop{\mathrm{\sf{ CHAIN}}}\), it is an intersection bigraph of rays \({\mathcal{R}}\) and points \({\mathcal{P}}\) where \(a \in A\) is mapped to \(r_a \in {\mathcal{R}}\) and \(b \in B\) to \(p_b \in {\mathcal{P}}\). Assume w.l.o.g. that \({\mathcal{P}}= \{1,\ldots, q\}\) for \(q \leq n\).

For each dyadic range \(\nu \in {\mathcal{D}}(q)\), we have an auxiliary graph \(G_{\nu}\) which is an induced subgraph \(G[A_{\nu} \cup B_{\nu}]\) where \(A_{\nu} = \{a \in A: \nu \in \sf{ dy}(r_a)\}\) and \(B_{\nu} = \{b: p_b \in \nu \}\). Notice that \(|E(G)| \leq \sum_{\nu \in {\mathcal{D}}(n)} |E(G_{\nu})|\).

Moreover, \(G_{\nu} = G'[A_{\nu} \cup B_{\nu}] \cap \widehat{G}[A_{\nu} \cup B_{\nu}]\) where \(G'[A_{\nu} \cup B_{\nu}]\) is a biclique; therefore \(G_{\nu} \in \mathop{\mathrm{\sf{ CHAIN}}}^{d-1}\) and is free of \(k\)-by-\(k\) biclique. This allows us to invoke the induction hypothesis, which implies that \[|E(G)| \leq \sum_{\nu \in {\mathcal{D}}(n)} O(|A_{\nu}| + |B_{\nu}|)k \lceil \log n\rceil^{d-4}\] Finally, since each vertex \(a \in A\) appears in at most \(\lceil \log q \rceil \leq \lceil \log n\rceil\) sets \(A_{\nu}\) (and similarly for each vertex \(b \in B\)), this implies that the above sum is at most \(O(|A|+ |B|)k \lceil \log n\rceil^{d-3}\). ◻

Proof. Since \(G \in \mathop{\mathrm{\sf{ CONV}}}^2\), then there exist graphs \(G_1\) and \(G_2\), such that \(G_1 \cap G_2 = G\). Let \(V_1\) and \(V_2\) be the partitions that the graphs \(G_1\) and \(G_2\), respectively, are convex over, and \(U_1 \subseteq V(G_1)\), \(U_2 \subseteq V(G_2)\), the other partitions.

Since \(\mathop{\mathrm{\sf{ CONV}}}\) graphs are closed under taking induced subgraphs, we can assume that \(U_1 \cup V_1 = U_2 \cup V_2\). Let \(A_1 = U_1 \cap U_2\), \(A_2 = U_1 \cap V_2\), \(B_1 = V_1 \cap V_2\), \(B_2 = V_1 \cap U_2\), as shown on ¿fig:fig:partition95intersections?.

We have \(U \cup V = A_1 \cup A_2 \cup B_1 \cup B_2\) and all edges must start and end at these nodes. Since \(A_1\) is in the same partition as \(A_2\), and \(B_2\), in at least one of the graphs, there can be no edges between \(A_1\) and \(A_2 \cup B_2\). The same is true for \(B_1\). Clearly, \(G\) can have one component consisting of nodes \(A_1 \cup B_1\) and another component consisting of nodes \(A_2 \cup B_2\), with no edges between these components.

It remains to see that \(G[A_1 \cup B_1] \in \mathop{\mathrm{\sf{ PRIG}}}\) and \(G[A_2 \cup B_2] \in \mathop{\mathrm{\sf{ GIG}}}\). To do this, we show that there exist representations of these graphs in \(\mathop{\mathrm{\sf{ PRIG}}}\) and \(\mathop{\mathrm{\sf{ GIG}}}\) respectively, such that the projections of these representations to \(x\) and \(y\) axis are the convex representations of graphs \(G_1\) and \(G_2\) induced on \(A_1 \cup B_1\) and \(A_2 \cup B_2\) respectively.

Let \(H_1 = G_1[A_1 \cup B_1]\) and \(H_2 = G_2[A_1 \cup B_1]\). Since \(G_1\) and \(G_2\) are convex over \(V_1\) and \(V_2\), and \(B_1 = V_1 \cap V_2\), then \(H_1\) and \(H_2\) are convex over \(B_1\). Let \((\mathbf{X}_1, \mathbf{Y}_1, \phi_1)\) be the point-segment representation of \(H_1\), such that \(\mathbf{Y}_1\) are the points. Then \(\phi_1: A_1 \mapsto \mathbf{X}_1, B_1 \mapsto \mathbf{Y}_1\). Let \((\mathbf{X}_2, \mathbf{Y}_2, \phi_2)\) be the point-segment representation of \(H_2\), such that \(\mathbf{Y}_2\) are the points. Then \(\phi_2: A_1 \mapsto \mathbf{X}_2, B_1 \mapsto \mathbf{Y}_2\). We construct a mapping \(\phi: A_1 \mapsto \mathbf{X}, B_1 \mapsto \mathbf{Y}\), where \(\mathbf{X}\) is a set of rectangles, and \(\mathbf{Y}\) a set of points in \(\mathbb{R}^2\). For each \(w \in A_1 \cup B_1\), \(\phi(w)\) is the object whose projection to the \(x\)-axis is \(\phi_1(w)\) and whose projection to the \(y\)-axis is \(\phi_2(w)\). Note that for all \(a \in A_1\), \(\phi(a)\) is a rectangle, and for all \(b \in B_1\), \(\phi(b)\) is a point. It is easy to verify that \(\phi(a)\) intersects \(\phi(b)\), if and only if \(\phi_1(a)\) intersects \(\phi_1(b)\) and \(\phi_2(a)\) intersects \(\phi_2(b)\), which implies that there is an edge \(\{a, b\}\) in the graph represented by \(\phi\), if and only if \(\{a, b\} \in E(H_1)\cap E(H_2)\). This means that \((\mathbf{X}, \mathbf{Y}, \phi)\) is a valid representation of \(G[A_1 \cup B_1] \in \mathop{\mathrm{\sf{ PRIG}}}\).

Showing that \(G[A_2 \cup B_2] \in \mathop{\mathrm{\sf{ GIG}}}\) is similar, but not quite symmetric. Let \(H_1 = G_1[A_2 \cup B_2]\) and \(H_2 = G_2[A_2 \cup B_2]\). Since \(G_1\) and \(G_2\) are convex over \(V_1\) and \(V_2\), and \(A_2 \subseteq V_2\), \(B_2 \subseteq V_1\), then \(H_1\) and \(H_2\) are convex over \(A_2\) and \(B_2\) respectively. Let us define \((\mathbf{X}_1, \mathbf{Y}_1, \phi_1)\) to be the point-segment representation of \(H_1\), such that \(\mathbf{X}_1\) are the points. Then \(\phi_1: A_2 \mapsto \mathbf{X}_1, B_2 \mapsto \mathbf{Y}_1\). Let \((\mathbf{X}_2, \mathbf{Y}_2, \phi_2)\) be the point-segment representation of \(H_2\), such that \(\mathbf{Y}_2\) are the points. Then \(\phi_2: A_2 \mapsto \mathbf{X}_2, B_2 \mapsto \mathbf{Y}_2\). We construct a mapping \(\phi: A_2 \mapsto \mathbf{X}, B_2 \mapsto \mathbf{Y}\), where \(\mathbf{X}\) is a set of horizontal segments, and \(\mathbf{Y}\) is a set of vertical segments in \(\mathbb{R}^2\).

For each \(w \in A_2 \cup B_2\), \(\phi(w)\) is the object whose projection to the \(y\)-axis is \(\phi_1(w)\) and whose projection to the \(x\)-axis is \(\phi_2(w)\). Note that for all \(a \in A_2\), \(\phi(a)\) is a horizontal segment and for all \(b \in B_1\), \(\phi(b)\) is a vertical segment. It is easy to verify that \(\phi(a)\) intersects \(\phi(b)\), if and only if \(\phi_1(a)\) intersects \(\phi_1(b)\) and \(\phi_2(a)\) intersects \(\phi_2(b)\), which implies that there is an edge \(\{a, b\}\) in the graph represented by \(\phi\), if and only if \(\{a, b\} \in E(H_1)\cap E(H_2)\). This means that \((\mathbf{X}, \mathbf{Y}, \phi)\) is a valid representation of \(G[A_1 \cup B_1] \in \mathop{\mathrm{\sf{ GIG}}}\). ◻

Proof. Let \(G\), \(G'\) be any disjoint graphs in \(\mathop{\mathrm{\sf{ CONV}}}^2\). Then we have graphs \(G_1, G_2 \in \mathop{\mathrm{\sf{ CONV}}}\), such that \(G_1 \cap G_2 = G\), and graphs \(G'_1, G'_2 \in \mathop{\mathrm{\sf{ CONV}}}\), such that \(G'_1 \cap G'_2 = G'\). Since \(\mathop{\mathrm{\sf{ CONV}}}\) is closed under disjoint union, then \(G_1 \mathbin{\dot{\cup}}G'_1 \in \mathop{\mathrm{\sf{ CONV}}}\) and \(G_2 \mathbin{\dot{\cup}}G'_2 \in \mathop{\mathrm{\sf{ CONV}}}\). Then \((G_1 \mathbin{\dot{\cup}}G'_1 )\cap (G_2 \mathbin{\dot{\cup}}G'_2) \in \mathop{\mathrm{\sf{ CONV}}}^2\). Since \(G_1\) only shares vertices with \(G_2\), and similarly, \(G'_1\) only shares vertices with \(G'_2\), then \((G_1 \mathbin{\dot{\cup}}G'_1 )\cap (G_2 \mathbin{\dot{\cup}}G'_2) = (G_1 \cap G_2) \mathbin{\dot{\cup}}(G'_1 \cap G'_2) = G \mathbin{\dot{\cup}}G' \in \mathop{\mathrm{\sf{ CONV}}}^2\). ◻

Proof. Let \(G = (U \cup V, E)\) be any graph in \(\mathop{\mathrm{\sf{ PRIG}}}\), and \((\mathbf{X}, \mathbf{Y}, \phi)\) the representation of \(G\) in \(\mathop{\mathrm{\sf{ PRIG}}}\), such that \(\mathbf{X}\) is a set of points and \(\mathbf{Y}\) a set of rectangles in \(\mathbb{R}^2\). Then we can construct mappings \(\phi_1\) and \(\phi_2\), such that for all \(w \in V(G)\), \(\phi_1(w)\) and \(\phi_2(w)\) are the projections of \(\phi(w)\) to \(x\) and \(y\) axis respectively. Let \(G_1\) and \(G_2\) be the graphs represented by \(\phi_1(w)\) and \(\phi_2(w)\) respectively. Since \(\phi_1(w)\) maps the vertices \(V(G)\) to points and segments based on their partitions, then \(G_1\in \mathop{\mathrm{\sf{ CONV}}}\). Similarly for \(G_2\). Since for any \(u \in U\), \(v \in V\), we have that \(\phi(u)\) intersects \(\phi(v)\) if and only if \(\phi_1(u)\) intersects \(\phi_1(v)\) and \(\phi_2(u)\) intersects \(\phi_2(v)\), then \(G_1 \cap G_2 = G\). This proves that \(G \in \mathop{\mathrm{\sf{ CONV}}}^2\). ◻

Proof. The proof is symmetric to 13. ◻

Proof. We are given \(G = (U \cup V, E) \in \mathop{\mathrm{\sf{ CHAIN}}}\) with a point ray representation \((\mathbf{X}, \mathbf{Y}, \phi)\), \(\phi: U \mapsto \mathbf{X}, V \mapsto \mathbf{Y}\), where \(\mathbf{X}\) represents points and \(\mathbf{Y}\) represents rays extending to \(\infty\) in \(\mathbb{R}\). For \(\nu\in \mathbf{Y}\), let \(\nu.p\) denote the minimum point in ray \(\nu\). Then for all \(u\in U\), \(v \in V\), we say that \(\phi(v).p < \phi(u)\), if and only if \(\{u, v\} \in E\).

We construct \((\mathbf{X}', \mathbf{Y}', \phi')\) such that for each \(u \in U\), \(\phi'(u) = (-\infty, \phi(u)]\), \(\phi'(v) = \phi(v).p\). Then for all \(u\in U\), \(v \in V\), \(\phi'(u)\) and \(phi'(v)\) intersect if \(\phi'(v) < \phi'(u).p\), which happens if and only if \(\phi(v).p < \phi(u)\). This implies that \((\mathbf{X}', \mathbf{Y}', \phi')\) is a representation of \(G\), where the partition \(U\) is mapped to rays and \(V\) to points. By flipping the representation, it is easy to see that there is an equivalent representation where rays extend to \(\infty\). ◻

Proof. Let \(({\mathcal{S}}, {\mathcal{B}}, \phi)\) be a segment bottomless rectangle representation of graph \(G = (U \cup V, E)\), such that \(\phi: U \mapsto {\mathcal{S}}, V \mapsto {\mathcal{B}}\). We will see that \(G \in \mathop{\mathrm{\sf{ CHAIN}}}^3\).

First, we consider the graph \(G_x = (U \cup V, E_x)\) represented by the projections of \({\mathcal{S}}, {\mathcal{B}}\) to the \(x\) axis. Since \(G_x\) is an interval containment bigraph, then \(G_x \in \mathop{\mathrm{\sf{ CHAIN}}}^2\) ([32], [6]). Secondly, consider the graph \(G_y = (U \cup V, E_y)\) represented by the projections of \({\mathcal{S}}, {\mathcal{B}}\) to the \(y\) axis. Since \(G_y\) is an intersection graph of points and rays, then \(G_y \in \mathop{\mathrm{\sf{ CHAIN}}}\). Since each \(b \in {\mathcal{B}}\) contains \(s \in {\mathcal{S}}\) if and only if \(s.x \subseteq b.x\) and \(s.y \subseteq b.y\), then \(G = G_x \cap G_y \in \mathop{\mathrm{\sf{ CHAIN}}}^2 \cdot \mathop{\mathrm{\sf{ CHAIN}}}= \mathop{\mathrm{\sf{ CHAIN}}}^3\).

Next, we will show that any graph \(G = (U \cup V, E) \in \mathop{\mathrm{\sf{ CHAIN}}}^3\) has a segment bottomless rectangle representation. According to [6], there exist graphs \(G_x = (U \cup V, E_x)\in \mathop{\mathrm{\sf{ CHAIN}}}^2\) and \(G_y = (U \cup V, E_y)\in \mathop{\mathrm{\sf{ CHAIN}}}\), such that \(G_x \cap G_y = G\). Let \((\mathbf{X}_x, \mathbf{Y}_x, \phi_x)\) be an interval containment representation of \(G_x\), such that \(\mathbf{X}\) represent the contained segments and \(\mathbf{Y}\) the containing ones. Let us consider the case that \(\phi_x: U \mapsto \mathbf{X}_x, V \mapsto \mathbf{Y}_x\), the case that \(\phi_x: V \mapsto \mathbf{X}_x, U \mapsto \mathbf{Y}_x\) is symmetric. Let \((\mathbf{X}_y, \mathbf{Y}_y, \phi_y)\) be a point ray representation of \(G_y\), such that \(\mathbf{X}_y\) are points and \(\mathbf{Y}_y\) are rays, \(\phi_y: U \mapsto \mathbf{X}_y, V \mapsto \mathbf{Y}_y\) ([lem:int95cont95symmetric]).

We construct a segment bottomless rectangle representation \(({\mathcal{S}}, {\mathcal{B}}, \phi)\), \(\phi: U \mapsto {\mathcal{S}}, V \mapsto {\mathcal{B}}\), such that for all \(w \in U \cup V\), \(\phi(w).x = \phi_x(w)\), \(\phi(w).y = \phi_y(w)\). Let \(G'\) be the graph represented by \(({\mathcal{S}}, {\mathcal{B}}, \phi)\). For all \(u \in U\), \(v \in V\), \(\phi(u)\) is contained within \(\phi(v)\) if and only if \(\phi_x(u)\) is contained within \(\phi_x(v)\) and \(\phi_y(u)\) is contained within \(\phi_y(v)\). This implies that \(G' = G_x \cap G_y\), which means that \(({\mathcal{S}}, {\mathcal{B}}, \phi)\) is a representation of \(G\). ◻

Proof. The number of stingy nodes is at least \(2(k-1)\). Let the stingy subset of \(S\) be \(S'\). For any \(\sigma\in S'\), there are at least \(k-1\) segments in either \(\mathop{\mathrm{DIR}}_{up}(\sigma)\cap S'\) or \(\mathop{\mathrm{DIR}}_{down}(\sigma)\cap S'\).

Let \(\sigma\in S'\) be the segment with the smallest \(\max(\sigma.x)\). Let \(\mathop{\mathrm{DIR}}_{down}(\sigma)\cap S' = S'_{down}\) and \(\mathop{\mathrm{DIR}}_{up}(\sigma)\cap S' = S'_{up}\). We consider the case that \(|S'_{down}| \geq k-1\). The case that \(|S'_{up}| \geq k-1\) is symmetric. Let \(Q\) be the \((k-1)\) rightmost down-heavy vertical segments in 7, that are each paid \(\frac{9}{2}\) credits from \(\sigma\). Let \(\nu' \in Q\) be the vertical segment with the largest \(\min(\nu'.y)\).

Since \(\nu' \in Q\) has the largest \(\min(\nu'.y)\) and \(\sigma\in S'\) has the smallest \(\max(\sigma.x)\), then \(\{\sigma\} \cup S'_{down} \cap N(v')\) and \(Q \cup \{\nu\}\) induce a biclique (11). Since \(|Q \cup \{\nu\}| = k\) and there cannot exist a \(K_{k, k}\), then \(|S'_{down} \cap N(v')| \leq k-2\), which implies that \(\min(\nu'.y)\) is greater than \(\min(S.y)\) (\(\nu'\) does not extend far enough down to include \(k-1\) stingy nodes below \(\sigma\)).

Since \(\nu'\) is down-heavy w.r.t \(\sigma\), then \(|N(\nu') \cap \mathop{\mathrm{DIR}}_{down}(\sigma)| \geq 3(k-1)\) (1). Let \(\Gamma = N(\nu') \cap \mathop{\mathrm{DIR}}_{down}(\sigma)\). Note that \(\Gamma.y \subseteq S.y\), because \(\min(\nu'.y)\) is greater than \(\min(S.y)\) and \(\max(\Gamma.y) < \sigma.y\). Due to how \(S\) was chosen (the last condition), this implies that the nodes in \(\Gamma\) that intersect \(\nu\) are in \(S\).

Since \((k-1)\) nodes of \(S'_{down} = \mathop{\mathrm{DIR}}_{down}(\sigma)\cap S'\) cannot be in \(N(\nu')\), then \(|\Gamma \cap S'| \leq k-2\). Since \(|S - S'| \leq k-2\), then \(|\Gamma - S| \geq 3(k-1) - (k-2) - (k-2) = k+1\).

Let us consider the conditions for \(S^* = \Gamma - S\). Since \(\Gamma \in N(\nu')\), \(\nu' \in Q \subseteq \mathop{\mathrm{DIR}}_{right}(\nu)\), and none of \(\Gamma - S\) intersect \(\nu\), then \(\Gamma - S \in \mathop{\mathrm{DIR}}_{right}(\nu)\). We already saw that \(|\Gamma - S| \geq k-1\) and \(\Gamma.y \subseteq S.y\). Since \(\sigma\in S'\) is the segment with the smallest \(\max(\sigma.x)\), then all intervals in \(S'\) projected to the \(x\) axis must include \(\nu'.x\). We have \(\nu'.x \in \bigcap_{\sigma\in S' \cup \Gamma} \sigma.x\), which fulfills the last condition. ◻

Proof. The proof is symmetric to 15. ◻

Proof. If \(S\) contains at least \((k-1)\) generous nodes, which each contribute at least \(\frac{9}{2}\) credits (\(\ref{alg:close95type}\)), the lemma holds. Otherwise, let \(S'\) be the set of stingy nodes in \(S\). We have that \(|S - S'| \leq k-2\).

Let \(R \in \mathop{\mathrm{DIR}}_{right}(\nu)\) be the set of nodes such that \(R.y \subseteq S.y\) and for each \(\sigma' \in R\), \(\sigma'.x\) intersects \(\bigcap_{\sigma\in S'} \sigma.x\). According to 15, \(|R| \geq k-1\). Let \(\hat{R}\) be the \(k-1\) segments \(\sigma\in R\) with the smallest \(\min(\sigma.x)\).

We will see that 8 pays \(\frac{9}{4}\) credits to \(\nu\) from every segment \(\sigma\in \hat{R}\). Let \(\sigma\in \hat{R}\) be an arbitrary segment. Let \(\mathop{\mathrm{DIR}}_{down}(\sigma)\cap S' = S'_{down}\) and \(\mathop{\mathrm{DIR}}_{up}(\sigma)\cap S' = S'_{up}\). Since \(|S'| \geq 3(k-1) - (k-2) = 2k - 1\), then either \(|S'_{down}| \geq k\) or \(|S'_{up}| \geq k\). We consider the case that \(|S'_{down}| \geq k\). The case that \(|S'_{up}| \geq k\) is symmetric. Let \(Q \subseteq \mathop{\mathrm{DIR}}_{left}(\sigma)\) be the \((k-1)\) rightmost down-heavy vertical segments in 8, that are each paid \(\frac{9}{4}\) credits from \(\sigma\). Note that if \(\nu\in Q\), then we have shown that 8 pays \(\frac{9}{4}\) credits to \(\nu\) from \(\sigma\). Since, according to our choice of \(S\), it is not among the lowest neighbors of \(N(\nu)\), then \(\nu\) is down-heavy concerning \(\sigma\). This implies that \(\nu\in Q\), unless all nodes of \(Q\) are to the right of \(\nu\). Since we have reached our goal in the case of \(\nu\in Q\), let us now consider only the case that \(Q \in \mathop{\mathrm{DIR}}_{right}(\nu)\) (12). Let \(\nu' \in Q\) be the vertical segment with the largest \(\min(\nu'.y)\).

Since \(\nu\) and some point in \(\sigma.x\) must intersect \(\bigcap_{\sigma' \in S'_{down}}\sigma'.x\) on the \(x\) axis, then all segments in \(Q\) (which are between them) also intersect all segments in \(S'\) when projected to the \(x\)-axis. Since \(\nu' \in Q\) has the largest \(\min(\nu'.y)\), then \(S'_{down} \cap N(v')\) and \(Q \cup \{\nu\}\) induce a biclique (12). Since \(|Q \cup \{\nu\}| = k\) and there cannot exist a \(K_{k, k}\), then \(|S'_{down} \cap N(v')| \leq k-1\), which implies that \(\min(\nu'.y)\) is greater than \(\min(S.y)\) (\(\nu'\) does not extend far enough down to include \(k\) stingy nodes below \(\sigma\)).

Since \(\nu'\) is down-heavy w.r.t \(\sigma\), then \(|N(\nu') \cap \mathop{\mathrm{DIR}}_{down}(\sigma)| \geq 3(k-1)\) (1). Let \(\Gamma = N(\nu') \cap \mathop{\mathrm{DIR}}_{down}(\sigma)\). Note that \(\Gamma.y \subseteq S.y\), because \(\min(\nu'.y)\) is greater than \(\min(S.y)\) and \(\max(\Gamma.y) < \sigma.y\). Due to how \(S\) was chosen (the last condition), this implies that the nodes in \(\Gamma\) that intersect \(\nu\) are in \(S\). Since \(k\) nodes of \(S'_{down} = \mathop{\mathrm{DIR}}_{down}(\sigma)\cap S'\) cannot be in \(N(\nu')\), then \(|\Gamma \cap S'| \leq k-1\). Since \(|S - S'| \leq k-2\), then \(|\Gamma - S| \geq 3(k-1) - (k-1) - (k-2) = k\).

Since all nodes that intersect \(\nu\) in \(\Gamma\), must be in \(S\), then \(\Gamma - S = \Gamma \cap \mathop{\mathrm{DIR}}_{right}(\nu) \cup \Gamma \cap \mathop{\mathrm{DIR}}_{left}(\nu)\). Since, according to our assumption, \(\nu' \in Q \subseteq \mathop{\mathrm{DIR}}_{right}(\nu)\), then no horizontal segment in \(\Gamma \in N(\nu')\) can be to the left of \(\nu\) without intersecting \(\nu\). Let \(\hat{\Gamma} = (\Gamma - S)\cap \mathop{\mathrm{DIR}}_{right}(\nu)\). Then we have \(|\hat{\Gamma}| \geq k\).

As discussed, when projected to the \(x\)-axis, all segments in \(Q\) intersect all segments in \(S'\). We have \(\nu' \in Q\) and \(\Gamma \in N(\nu')\). Therefore, on the \(x\)-axis, we have a point \(\nu'.x\) that intersects \(S'\) as well as \(\Gamma\). According to how we defined \(R\), we have \(\hat{\Gamma} \subseteq R\).

Since for all \(\sigma^* \in \Gamma\), \(\min(\sigma^*.x) \leq v'.x < \min(\sigma.x)\), then \(\hat{R}\) contains \(\hat{\Gamma}\), if it contains \(\sigma\). This implies that \(|\hat{R}| \geq k\), which is a contradiction, since we chose \(\hat{R}\) such that it would only contain \(k-1\) segments. This implies that the case that \(v \not \in Q\) is impossible.

Let \(L \in \mathop{\mathrm{DIR}}_{left}(\nu)\) be the set of nodes such that \(L.y \subseteq S.y\) and for each \(\sigma' \in L\), \(\sigma'.x\) intersects \(\bigcap_{\sigma\in S'} \sigma.x\). According to 16, \(|L| \geq k-1\). Let \(\hat{L}\) be the \(k-1\) segments \(\sigma\in L\) with the largest \(\max(\sigma.x)\). The proof that 8 pays \(\frac{9}{4}\) credits to \(\nu\) from every segment \(\sigma\in \hat{L}\) is symmetric. ◻

Proof. Let \(G = (U \cup V, E)\) be any \(K_{2, 2}\)-free graph in \(\mathop{\mathrm{\sf{ PRIG}}}\), and \((\mathbf{X}, \mathbf{Y}, \phi)\) the representation of \(G\) in \(\mathop{\mathrm{\sf{ PRIG}}}\), such that \(\phi: U \mapsto \mathbf{X}, V \mapsto \mathbf{Y}\), \(\mathbf{X}\) is a set of points and \(\mathbf{Y}\) a set of rectangles in \(\mathbb{R}^2\). We construct a new graph \(G = (U' \cup V', E')\), that is represented in \(\mathop{\mathrm{\sf{ PRIG}}}\) by \((\mathbf{X}', \mathbf{Y}', \phi')\), \(\phi: U' \mapsto \mathbf{X}', V' \mapsto \mathbf{Y}'\) as follows. For every \(\sigma\in \mathbf{X}\), we create \(k-1\) copies in \(\mathbf{X}'\), and for every \(\nu\in \mathbf{Y}\), we create \(k-1\) copies in \(\mathbf{Y}'\). It is easy to see that \(|U'| = (k-1) |U|\), \(|V'| = (k-1) |V|\). Let us see the number of edges. For every \(u \in U\), \(\phi(u)\) intersects with \(|N(u)|\) rectangles in \(G\). In \(G'\), a copy of \(\phi(u)\) intersects with all the copies of \(\phi(N(u))\), which number in \((k-1) \cdot |N(u)|\). Let \(u'\) be a node in \(G'\) that is represented by a copy of \(\phi(u)\). The degree of \(u'\) is \(k-1\) times larger than the degree of \(u\). Since the number of nodes in \(U'\) is also \(k-1\) times larger than in \(U\), then \(|E'| = |E| \cdot (k-1)^2\).

Finally, let us see that \(G'\) is \(K_{k, k}\)-free. Suppose by contradiction that \(G'\) has \(K_{k, k}\) as a subgraph. Let \(S_U \subseteq U'\) and \(S_V \subseteq V'\) be the nodes that induce \(K_{k, k}\) in \(G'\). Then there must be at least two nodes \(u, u^* \in U\), whose copies form \(S_U\), and at least two nodes \(v, v^* \in V\) whose copies form \(S_V\). Since \(G'[S_U \cup S_V]\) is a biclique, then it has edges between all pairs of nodes. There can be an edge between a pair of nodes \(\{u', v'\}\), \(u'\in U'\), \(v' \in V'\), if and only if that edge existed in \(G\) between the nodes whose copies \(u'\) and \(v'\) are. This implies that \(u, u^* \in U\) and \(v, v^* \in V\) must have induced a \(K_{2, 2}\) in \(G\). This is a contradiction. ◻

Proof. Consider a chain graph \(G= (U \cup V, E)\) where \(V\) corresponds to the rightward rays \(\{r_1, r_2, \ldots, r_{n}\}\) and \(U\) to the points \(\{p_1, p_2, \ldots, p_{m}\}\). Let all the points be placed on the real line such that each point \(p_i\) is at coordinate \(i\). The rays \(r_1,\ldots, r_{k-1}\) start at the coordinate \(0\), which contains all the points. The remaining rays \(r_k, \ldots, r_{n}\) start at coordinate \((m-k+1.5)\), so they contain \(k-1\) points (see 13). Clearly, the graph does not contain a biclique \(K_{k,k}\). The number of edges is \(n(k-1) + (m-k+1)(k-1) = (n+m)(k-1)-(k-1)^2\). ◻