Unavoidable Patterns and Plane Paths in Dense Topological Graphs

Label each vertex $v$ of $G$ by the four-tuple $(l_1,l_2,l_3,l_4)$, where $l_i$ is the edge number of the longest monotone path in color $i$ ending at $v$. If any of these paths have at least $m$ edges we are done. If this is not the case, then all the labels are from ${\{0,\mathrm{\dots },m-1\}}^4$, so by the pigeonhole principle, some $t+1$ vertices must share the same label. We claim that these vertices induce a monochromatic clique in the fifth color. Indeed, assume the vertex $u$ precedes vertex $v$ in the vertex order and the edge $uv$ receives color $i$. Consider the longest monotone path in color $i$ ending at $u$. Extending this path with the $uv$ edge we get a longer monotone path in color $i$ ending at $v$ showing that $u$ and $v$ cannot share the same label unless $i=5$. This proves the lemma. $◀$

Let $r(k;r)$ be the minimum integer $n$ such that every $r$-coloring of the edges of the complete graph on $n$ vertices contains a monochromatic clique on $k$ vertices. The existence of $r(k;r)$ follows by the famous theorem of Ramsey [24], and following the arguments of Erdős–Szekeres [9], we have

Let $G$ be a complete bipartite simple topological graph whose vertex set is $U\cup V$, where $|U|=m>2{(k-1)}^4$ and $|V|=n\ge 2^{k^{5k}}$. We assume without loss of generality that $m=2{(k-1)}^4+1$ (otherwise we simply ignore the extra vertices in $U$). There is nothing to prove when $k=1$. When $k=2$, since $K_{3,3}$ is not planar, we can find a pair of crossing edges $u_1{v}_1$ and $u_2{v}_2$ in $G$, and as $G$ is simple, the induced topological subgraph on $u_1,u_2,v_1,v_2$ is weakly isomorphic to $C_{2,2}$. Therefore, we assume $k\ge 3$ for the rest of this proof.

By arbitrarily ordering the elements in $U$ and $V$, we have $U=\{u_1,\mathrm{\dots },u_m\}$, and $V=\{v_1,\mathrm{\dots },v_n\}$. For each 4-tuple $u_i,u_j\in U$ and $v_s,v_t\in V$, where and , let us consider the drawing of $K_{2,2}$ induced on these vertices. Note that as we have a simple topological graph, only non-adjacent edges can cross, that is, $u_i{v}_s$ may cross $u_j{v}_t$ or $u_i{v}_t$ may cross $u_j{v}_s$. If both of these pairs of edges cross, then we obtain a thrackle drawing of $C_4$ and a small case-analysis shows that such a drawing does not exist. So we have three possibilities, either the first pair cross, or the second pair, or it is a plane drawing. We further refine this classification according to the orientation of the vertices around the crossing point obtaining the following five order types. When speaking about the order of the vertices around the crossing point we mean the cyclic order of the edge-segments going to these vertices.

1. 1.

   The 4-tuple $\{u_i,u_j,v_s,v_t\}$ is of type 1 if edge $u_i{v}_t$ crosses edge $u_j{v}_s$, and moreover, vertices $(u_i,v_s,v_t,u_j)$ appear in clockwise order from the crossing point of $u_i{v}_t$ and $u_j{v}_s$.

2. 2.

   The 4-tuple $\{u_i,u_j,v_s,v_t\}$ is of type 2 if edge $u_i{v}_t$ crosses edge $u_j{v}_s$, and moreover, vertices $(u_i,u_j,v_t,v_s)$ appear in clockwise order from the crossing point of $u_i{v}_t$ and $u_j{v}_s$.

3. 3.

   The 4-tuple $\{u_i,u_j,v_s,v_t\}$ is of type 3 if edge $u_i{v}_s$ crosses edge $u_j{v}_t$, and moreover, vertices $(u_i,v_t,v_s,u_j)$ appear in clockwise order from the crossing point of $u_i{v}_s$ and $u_j{v}_t$.

4. 4.

   The 4-tuple $\{u_i,u_j,v_s,v_t\}$ is of type 4 if edge $u_i{v}_s$ crosses edge $u_j{v}_t$, and moreover, vertices $(u_i,u_j,v_s,v_t)$ appear in clockwise order from the crossing point of $u_i{v}_s$ and $u_j{v}_t$.

5. 5.

   The 4-tuple $\{u_i,u_j,v_s,v_t\}$ is of type 5 if it induces a plane drawing of $K_{2,2}$.

See Figure 1. For $v_s,v_t\in V$ and $w\in \{1,2,3,4,5\}$, let $G_{s,t}^{(w)}$ be the ordered graph whose vertex set is $U$, and edges are pairs of vertices $\{u_i,u_j\}$ such that the 4-tuple $\{u_i,u_j,v_s,v_t\}$ is of type $w$.

We claim that the ordered graph $G_{s,t}^{(w)}$ is transitive for $w\in \{1,2,3,4\}$, that is, with respect to the first four order types. We verify the statement for $G_{s,t}^{(1)}$. For , suppose that $\{u_i,u_j\}$ and $\{u_j,u_{\mathrm{\ell }}\}$ are edges in $G_{s,t}^{(1)}$. Consider the drawing of $K_{2,2}$ induced by the 4-tuple $\{u_i,u_j,v_s,v_t\}$, specifically the “triangle” formed by $u_j$, $v_t$ and the crossing point between $u_j{v}_s$ and $u_i{v}_t$. Since $(u_j,v_s,v_t,u_{\mathrm{\ell }})$ must appear in clockwise order from the crossing point of $u_j{v}_t$ and $u_{\mathrm{\ell }}{v}_s$, we must exit the “triangle” at this crossing point as we travel along $u_{\mathrm{\ell }}{v}_s$ from $v_s$ to $u_{\mathrm{\ell }}$. This implies that $u_{\mathrm{\ell }}{v}_s$ crosses both $u_j{v}_t$ and $u_i{v}_t$. Further, $u_{\mathrm{\ell }}$, $v_s$, and $v_t$ must appear in the same cyclic order from the crossing point of $u_j{v}_t$ and $u_{\mathrm{\ell }}{v}_s$ as well as from the crossing point of $u_i{v}_t$ and $u_{\mathrm{\ell }}{v}_s$. The former is clockwise order from the assumption $\{u_j,u_{\mathrm{\ell }}\}\in E(G_{s,t}^{(1)})$, so the latter also clockwise implying $\{u_i,u_{\mathrm{\ell }}\}\in E(G_{s,t}^{(1)})$ as claimed. See Figure 2. The transitivity property of $G_{s,t}^{(2)},G_{s,t}^{(3)}$, and $G_{s,t}^{(4)}$ can be argued similarly, or be reduced to the case of $G_{s,t}^{(1)}$ by reversing the vertex orders on $U$ or $V$. For example, a type 3 quadruple $\{u_i,u_j,v_s,v_t\}$ would have been type 1 if we had ordered the vertices in $U$ the same but in $V$ reversely.

Since $|U|>2{(k-1)}^4$, by combining Lemmas 8, 9, and the fact that $G_{s,t}^{(w)}$ is transitive when $w\in \{1,2,3,4\}$, we have the following observation.

This claim implies that we can label the edge $v_s{v}_t$ of the complete graph on $V$ with a pair $(S,i)$, where $i\in \{1,\mathrm{\dots },5\}$ and $S\subset U$ is a clique in $G_{s,t}^{(i)}$ of size $3$ if $i=5$ or of size $k$ otherwise. In case there are more possible labels we choose arbitrarily. For $k\ge 7$, using $|U|=2{(k-1)}^4+1\le 2k^4$, the number of distinct labels we use on the edges is at most

And we can further estimate using $k\ge 7$

For $k=3,4,5,6$, the upper bound for $r(k)$ is too crude, but we can verify the previous inequality by direct computation.

Applying Lemma 10 together with $|V|\ge 2^{k^{5k}}$, there is a subset $T\subset V$ of size $k$ such that every pair in $T$ has the same label $(S,i)$. Let us consider the topological subgraph $G^{\prime }$ induced on $S\cup T$. The proof now falls into the following cases.

Case 1. Suppose $|S|=k$ and $i\in \{1,2,3,4\}$. We can assume that $i=1$, since a symmetric argument would follow otherwise. Then for $u_i,u_j\in S$ and $v_s,v_t\in T$, where and , $\{u_i,u_j,v_s,v_t\}$ is of type 1, and therefore, $u_i{v}_t$ crosses $u_j{v}_s$. Hence, $G^{\prime }$ is weakly isomorphic to $C_{k,k}$.

Case 2. Suppose $|S|=3$ and $i=5$. Then $G^{\prime }$ is a plane drawing of $K_{3,k}$. This is impossible as $k\ge 3$. $◀$

First, we argue that if a graph $G$ contains a vertex $v$ with at least three non-leaf neighbors, then $G$ is not geometric local thrackleable. See Figure 3 for two such graphs with $G_1$ already covered in [29]. Indeed, if $v$ has three non-leaf neighbors, then in any straight line drawing, one of them “splits” the neighborhood of $v$, that is, $v$ has neighbors in both sides of the line of the edge $vw$ for some non-leaf neighbor $w$. But as $w$ is no leaf it has another neighbor $w^{\prime }\ne v$ and in any local thrackle drawing $w{w}^{\prime }$ intersects (crosses or has a common endpoint with) every edge incident to $v$, which is only possible if $w$ does not split the neighborhood, a contradiction.

Let us remove all the leaves of a geometric local thrackleable graph $G$. The observation above implies that the remaining graph has maximum degree at most $2$, so it is the disjoint union of paths and cycles. This implies that $G$ is the disjoint union of caterpillars and spiked cycles. To finish the only if part of the proposition we are left to show that $C_4$ and $C_6$ are not geometric local thrackleable. It is easy to see that if $C_4$ is drawn as a local thrackle, then this drawing must be a thrackle. The same holds true for $C_6$ as we shall prove in Lemma 15 (although for straight line drawings the case analysis could be shortened). On the other hand, it follows from Theorem 12 that even cycles are not geometric thrackleable ($C_4$ is not even thrackleable), hence $C_4$ and $C_6$ are not geometric local thrackleable.

For the if part of proposition, notice that the components of $G$ can be drawn pairwise disjointly, so it is enough to prove that caterpillars, odd spiked cycles and even spiked cycles of length at least $8$ are geometric local thrackleable. The first two cases are already handled by Theorem 12 (as those graphs are geometric thrackleable), so here we concentrate on even spiked cycles. Let $n\ge 8$ be even. We first place vertices $v_1,v_2,\mathrm{\dots },v_{n-3}$ on the circle according to the following clockwise order: $v_1,v_3,v_5,\mathrm{\dots },v_{n-3}$, $v_2,v_4,\mathrm{\dots },v_{n-4}$. Then we put $v_{n-2}$ on the clockwise arc $v_1{v}_3$, $v_{n-1}$ on the clockwise arc $v_2{v}_4$, and $v_n$ on the clockwise arc $v_{n-5}{v}_{n-3}$. Observe that we obtain a geometric local threackle drawing of $C_n$ by connecting $v_i{v}_{i+1}$ using straight-line segments. See Figure 4 for an illustration. Finally, we can choose an interval on the cycle for each $v_i$ such that if we place the leaf neighbors of $v_i$ on this intervals the resulting drawing is still a local thrackle. $◀$

We continue with the case when edges are drawn $x$-monotone.

For the lower bound we give a construction with $6/5n-O(1)$ edges. See Figure 5. First, we draw a path as seen on the top of Figure 5 as a local thrackle. Then we make a translated copy of this path as seen on the middle of Figure 5, this is clearly still a local thrackle. Finally, we add further paths of length $2$, one of them is drawn blue on the middle of Figure 5, and moreover, one can check that adding this one path maintained that the drawing is a local thrackle. All such blue paths are drawn on the bottom of Figure 5, where it is not hard to check that the drawing gives a simple topological graph and also it is still a local thrackle (the blue $2$-paths are far enough in the graph, thus no planar $3$-path can be created when adding all blue $2$-paths, if adding one did not create a planar $3$-path), finishing the construction. Note that we connected using a $2$-path every second vertex of one path with the corresponding vertex of the second path, thus when extending the construction with $2$ vertices on each path plus a vertex to add the $2$-path joining, we added $5$ vertices and $6$ edges. Thus, the number of edges is $6/5n-O(1)$ (the constant error comes from the fact that close to the two ends of the two paths some edges are missing).

For the upper bound, let $G$ be a local thrackle with $x$-monotone edges. We may assume that every vertex has degree at least one. We distinguish three types of vertices. A vertex that has no edges going to the left (resp. right) is called a left-vertex (resp. right-vertex). A vertex that has edges in both directions is called a middle-vertex. Assume there are $l$ left-vertices, $r$ right-vertices and $m$ middle-vertices, $l+r+m=n$.

At each left-vertex, delete the incident edge that leaves highest at this vertex. Delete at each right-vertex the incident edge that leaves lowest at this vertex. We have deleted at most $l+r$ edges. Notice that if there is a remaining edge between a left-vertex and a right-vertex, then together with the $2$ deleted edges incident to these vertices, we get a plane $3$-path, a contradiction. Therefore, no edge is left between a left- and a right-vertex. Similarly, if a middle-vertex is connected to two left-vertices in the remaining graph, then adding the deleted edge of the left-vertex on the higher of these two edges, we obtain a plane $3$-path. The contradiction shows that every middle vertex is connected to at most one left-vertex in the remaining graph.

Next, we claim that the remaining edges connecting the left-vertices and middle-vertices form a matching. After the observation above it is enough to show that any left-vertex has at most one middle-vertex neighbor. Indeed, otherwise take two edges from a left-vertex to middle-vertices and two more edges going right from these middle-vertices. It is easy to see that one of the $3$-paths in the obtained $4$-path or $4$-cycle must be plane, a contradiction. Therefore, the number of remaining edges connecting left- and middle vertices is at most $\min (l,m)$.

Similarly, there are at most $\min (r,m)$ edges between the right-vertices and middle-vertices left in the graph. No edge connects two middle-vertices because that would lead to an $x$-monotone (therefore plane) $3$-path. Putting everything together, our original graph has at most $l+r+\min (l,m)+\min (r,m)$ edges. Assume without loss of generality that $r\le l$. Then this is at most $l+r+m+\min (l,r,m)=n+\min (l,r,m)\le n+n/3=4n/3$. $◀$

For the case of general local thrackles we need the following statements. Let ${\mathrm{\Theta }}_3$ denote a graph consisting of two vertices connected by three internally-disjoint paths of length three. That is, ${\mathrm{\Theta }}_3$ is a graph with 8 vertices and 9 edges.

Fulek and Pach [11] invented a computational approach to check whether a given graph is thrackleable. In fact, as we shall describe, their method is more general and can check whether any crossing pattern can be realized as a simple drawing or not. Let $G=(V,E)$ be an oriented graph. (We need the orientation for reference purposes only.) Suppose we are given an ordered list $\mathrm{\ell }(e)$ consisting of elements in $E\setminus e$ for each $e\in E$, with the property that $f\in \mathrm{\ell }(e)$ if and only if $e\in \mathrm{\ell }(f)$, then we can construct an auxiliary graph $H$ through the following procedure:

1. 1.

   (Planarization) For every $e\in E$ directed from $u$ to $v$, we replace the edge $e=\{u,v\}$ by a path from $u$ to $v$, through the vertices named as $\{e,f\}$ with $f\in \mathrm{\ell }(e)$ following the order of $\mathrm{\ell }(e)$. Here, we introduce new vertices $\{e,f\}$ if necessary.

2. 2.

   (Subdivision) For each edge between two new vertices created in the planarization step, we replace it with a path of length two, by inserting an additional vertex.

3. 3.

   (Bracing) For each new vertex $v=\{e,f\}$ created in the planarization step, there will be exactly four vertices $a,b,c,d$ adjacent to $v$ (they may be original vertices in $V$ or new vertices introduced in subdivision step), where $a,b$ are adjacent to $v$ along segments of of $e$ and $c,d$ are adjacent to $v$ along segments of $f$. We create the edges $\{a,c\}$, $\{a,d\}$, $\{b,c\}$, and $\{b,d\}$.

We remark that here $\{e,f\}$ is unordered, so it will be considered in the planarization steps for $e$ and $f$ respectively, which will give it exactly four neighbors.

We give a brief explanation to this claim. Suppose $G$ has such a drawing, then we can turn it into a plane drawing by turning each crossing point into a new vertex (planarization). Next, we can subdivide each edge between the crossing points once (subdivision). Finally, we connect the neighbors of each crossing point in their cyclic order (bracing). This can be done easily such that the resulting drawing is still plane, implying that $H$ is planar; On the other hand, suppose we have a plane drawing of $H$, we can draw any edge $e$ of $G$, directed from $u$ to $v$, along the path from $u$ to $v$ in $H$ created in planarization. The vertices created in the subdivision step serve as a guide on which path to follow at a crossing point. The bracing structures will enforce the edges drawn to cross properly without tangencies. This will give a drawing of $G$ as wanted.

Following this approach, we used a computer program to verify Lemma 15. To prove this lemma, it suffices for us to take $G=C_6$, direct its edges arbitrarily, create every possible crossing list $\mathrm{\ell }$ that obeys the local thrackle condition, construct $H$ and test for its planarity. If all such $H$ except for those corresponding to thrackles are not planar, then we can conclude the proof. A source code for such a computer program is given in the full version of this paper [16]. $◀$

We show the following strengthening of the above theorem:

Assume on the contrary, then ${\mathrm{\Theta }}_3$ can be drawn as a local thrackle. By Theorem 17 this is not a thrackle, therefore there are two independent edges that do not cross. The only way this can happen is that there is a subgraph $C_6$ drawn such that a pair of opposite edges do not cross. This is a local thrackle drawing of a $C_6$ which is not a thrackle drawing, contradicting Lemma 15, finishing the proof. $\mathrm{⊲}$

First we show that a $1$-subdivision of a star $S_n$ is local thrackleable. For that see Figure 7. Note that outside of an area that can be made arbitrarily small (the inside of the dotted circle on the figure), the edges incident to the center can be drawn close to each other and the edges incident to the leaves can be drawn parallel. That is, every $2$-path starting at $v_1$ goes very close to a given $2$-path (say the one joining $v_1$ to $w_1$) and only in a small vicinity of the middle vertex of this given $2$-path do these $2$-paths intersect each other. Note that the cyclic order of the paths around $v_i$ is reversed by the time they reach the $w_i$’s.

We have a drawing of the 1-subdivision of the star $S_n$ with center $v_1$ and leaves $W=\{w_1,\mathrm{\dots },w_n\}$. Now we draw $n$ copies of this graph so that the leaves are identified to get the drawing of the graph $G$ which is the $1$-subdivision of $K_{n,n}$. The way we do it is that we put $n-1$ more vertices, $v_2,\mathrm{\dots },v_n$, close to $v_1$ and draw the new edges in the following way. For each $w_i$, we had one $2$-path going to $v_1$ and we need $n-1$ more $2$-paths going to $v_2,\mathrm{\dots },v_n$. We draw them the same way as we created the original star, just now $w_i$ is the center and the $2$-path from $w_i$ to $v_1$ is the $2$-path close to which all the other $2$-paths go (and they only intersect in a small vicinity of the middle vertex of the $2$-path from $w_i$ to $v_1$). We denote $V=\{v_1,\mathrm{\dots }{v}_n\}$.

We draw the edges in the vicinity of $v_1$ such that they intersect pairwise at most once and two edges with a common endpoint $v_i$ do not cross. See Figure 7, the dashed rectangle is the vicinity of $v_1$ where such crossings happen.

Finally, we are left to prove that this is a local thrackle. It is easy to check we have a simple drawing. It remains to check that no 3-edge path is planar. For this, notice that any $3$-path contains exactly one vertex from $V$ and $W$ respectively. This implies that the $3$ edges of any $3$-path belong to a 1-subdivision of a star that was drawn as a local thrackle. For $v_1$ this follows from our drawing of $S_n$, for other $v_i$ it follows from the fact that these edges go close to the respective edge from $v_1$, and for $w_i$ it again follows from the fact that at $w_i$ we drew the edges in distance two as a local thrackle. $\mathrm{⊲}$

The upper bound directly follows from Theorem 14 and Claim 18. The lower bound follows from Claim 19 by observing that in a $1$-subdivision of $K_{n,n}$ we have $n^2+2n$ vertices and $2n^2$ edges. $◀$

Note that Claim 19 implies that the $3$-subdivision of $K_n$ is local thrackleable, which implies that the $3$-subdivision of any graph is local thrackleable. Therefore arguments that rely on forbidden subdivided copies of some graph (e.g., planarity arguments) won’t work when trying to improve the upper bound in Proposition 7.

In the full version of this paper [16] we give further examples of local thrackles.

A dual version of Proposition 6 was obtained by Pach, Pinchasi, Tardos, and Tóth in [21], who proved that every $n$-vertex $x$-monotone simple topological graph with no self-intersecting path of length 3 has at most $O(n\log n)$ edges. Moreover, they showed that this bound is asymptotically tight. For fixed $k\ge 3$, a construction due to Tardos [28] shows that there are geometric graphs with no self-intersecting path of length $k$ and with a superlinear number of edges. Pach, Pinchasi, Tardos, and Tóth in [21] also showed that every $n$-vertex topological graph (not necessarily simple) with no self-intersecting path of length 3 has at most $O(n^{3/2})$ edges. In the full version of the paper [16], we give a short proof of the following variant.

Two topological graphs $G$ and $H$ are isomorphic if there is a homeomorphism of the sphere that transforms $G$ to $H$, where this sphere is the one-point compactification of the plane we draw the graphs on. The proof of Theorem 1 finds more than a weak-isomorphic copy of $C_{k,k}$ any simple drawing of a large enough complete graph. The drawing of $K_{k,k}$ we find as a subgraph agrees with $C_{k,k}$ in its extended rotation system, that is, the cyclic orders of edges emanating from all vertices and crossings. According to Theorem 1 in the recent paper [2], this determines $H$ up to triangle flips followed by an isomorphism. Here, a triangle flip refers to the operation of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the two other edges.

The following 4-uniform hypergraph Ramsey problem was also studied independently by Negami [18] and Mathias Schacht (private communication). Let $S_{a,b}=(U,V,E)$ be the 4-uniform hypergraph with the vertex set the disjoint union of $U$ and $V$, where $|U|=a$ and $|V|=b$, such that $E(S_{a,b})=\{\{x,y,z,w\}:x\ne y,z\ne w,x,y\in U,\text{ and }z,w\in V\}.$ What is the minimum integer $r(S_{n,n})=N$ such that for any red/blue coloring of the edges of $S_{N,N}$, there is a monochromatic copy of $S_{n,n}$? Following the arguments given in Section 2, one can show that , while a standard probabilistic argument shows that $r(S_{n,n})>2^{\mathrm{\Omega }(n^3)}$.