Disjoint Edges in Complete Topological Graphs

Abstract

It is shown that every complete $n$-vertex simple topological graph has at $\varOmega (n^{1/3})$ pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Tóth, which appears as Problem 5 from Chapter 9.5 in Research Problems in Discrete Geometry by Brass, Moser, and Pach.

1 Introduction

Given a collection of objects $\mathcal C$ in the plane, the intersection graph $G(\mathcal C )$ has vertex set $\mathcal C$ and two objects are adjacent if and only if they have a nonempty intersection. The independence number of $G(\mathcal C )$ is the size of the largest independent set, that is, the size of the largest subfamily of pairwise disjoint objects in $\mathcal C$. It is known that computing the independence number of an intersection graph is NP-hard [12], even for very simple objects such as rectangles and disks in the plane [3, 11]. However, due to its applications in VLSI design [13], map labeling [1], and elsewhere, a lot of research has been devoted to developing polynomial-time approximation schemes (PTAS) for computing the independence number of intersection graphs (see [9] for more references). In this paper, we study the independence number of the intersection graph of edges in a complete simple topological graph.

A topological graph is a graph drawn in the plane such that its vertices are represented by points, and its edges are represented by non-self-intersecting arcs connecting the corresponding points. The arcs are allowed to intersect, but they may not intersect vertices except for their endpoints. Furthermore, no three edges have a common interior point and no two edges are tangent, i.e., if two edges share an interior point, then they must properly cross at that point in common. A topological graph is simple if every pair of its edges intersect at most once. Two edges of a topological graph cross if their interiors share a point, and are disjoint if they neither share a common vertex nor cross. If the edges are drawn as straight-line segments, then the graph is geometric.

Let $F$ denote the graph obtained from the complete graph on five vertices by subdividing each edge with an extra vertex. It is easy to see that every intersection graph $G$ of curves in the plane does not contain $F$ as an induced subgraph [6]. By applying a theorem of Erdős and Hajnal [7], every complete $n$-vertex simple topological graph contains $e^{\varOmega (\sqrt{\log n})}$ edges that are either pairwise disjoint or pairwise crossing. However, it was suspected [16] that this bound is far from optimal. Fox and Pach [8] showed that there exists a constant $\delta > 0$, such that every complete $n$-vertex simple topological graph contains $\varOmega (n^{\delta })$ pairwise crossing edges. However, much weaker bounds were previously known for pairwise disjoint edges.

In 2003, Pach et al. [16] showed that every complete $n$-vertex simple topological graph has at least $\varOmega (\log ^{1/6}n)$ pairwise disjoint edges. This lower bound was later improved by Pach and Tóth [17] to $\varOmega (\log n/\log \log n)$. Recently, Fox and Sudakov [10] gave a modest improvement of $\varOmega (\log ^{1 + \varepsilon }n)$, where $\varepsilon$ is a very small constant. We note that the previous two bounds hold for dense simple topological graphs. Pach and Tóth conjectured (see Problem 5 of Chapter 9.5 in [4]) that there exists a constant $\delta >0$ such that every complete $n$-vertex simple topological graph has at least $\varOmega (n^{\delta })$ pairwise disjoint edges. Our main result settles the conjecture in the affirmative.

Theorem 1.1

Every complete $n$-vertex simple topological graph contains $\varOmega (n^{1/3})$ pairwise disjoint edges.

Note that Theorem 1.1 does not remain true if the simple condition is dropped. Indeed, in [17], Pach and Tóth gave a construction of a complete $n$-vertex topological graph such that every pair of edges intersect exactly once or twice.

2 The Dual Shatter Function

In this section, we will recall one of the most useful parameters measuring the complexity of a set system: the dual shatter function. All of the following concepts and results can be found in Chapter 5 of [14]. Let $(X,\mathcal S )$ be a set system with ground set $X$, such that $X$ is finite.

Definition 2.1

The dual shatter function of $(X,\mathcal S )$ is a function, denoted by $\pi ^{*}_\mathcal{S }$, whose value at $m$ is defined as the maximum number of equivalence classes on $X$ defined by an $m$-element subfamily $\mathcal Y \subset \mathcal S$, where two points $x,y \in X$ are equivalent with respect to $\mathcal Y$ if $x$ belongs to the same sets of $\mathcal Y$ as $y$ does. In other words, $\pi ^*_\mathcal{S }(m)$ is the maximum number of nonempty cells in the Venn diagram of $m$ sets of $\mathcal S$.

One of the main tools used to prove Theorem 1.1 is the following result of Chazelle and Welzl on matchings with low stabbing number. A similar approach was done by Pach in [15], who showed that every $n$-vertex complete geometric graph contains $\varOmega (n^{1/2})$ pairwise parallel edges, where two edges are parallel if they are the opposite sides of a convex quadrilateral.

Given a set system $(X,\mathcal S )$ and a graph $G = (X,E)$, we say that a set $S \in \mathcal S$ stabs edge $uv \in E(G)$ if $|S\cap \{u,v\}| = 1$. The stabbing number of $G$ with respect to the set $S$ is the number of edges of $G$ stabbed by $S$, and the stabbing number of $G$ is the maximum of stabbing numbers of $G$ with respect to all sets of $\mathcal S$.

Lemma 2.2

([5]) Let $n$ be an even integer, and $\mathcal S$ be a set system on an $n$-point set $X$ with $\pi ^*_\mathcal{S }(m) \le Cm^d$ for all $m$, where $C$ and $d$ are constants. Then there exists a perfect matching $M$ on $X$ (i.e. a set of $n/2$ vertex disjoint edges) whose stabbing number is at most $C_1n^{1 - 1/d}$, where $C_1$ is a constant that depends only on $C$ and $d$.

We will also need the following two lemmas on the dual shatter function of a set system.

Lemma 2.3

Let $\mathcal S _{1},\mathcal S _{2}$ be set systems on a set $X$ and let $\mathcal S = \mathcal S _{1}\cup \mathcal S _{2}$. Then $\pi _\mathcal{S }^{*(m)} \le \pi _\mathcal{S _1}^{*(m)}\pi _\mathcal{S _2}^{*(m)}$.

Proof

Suppose that $\pi ^*_\mathcal{S }(m)$ is maximized for some $m_1$ sets in $\mathcal S _1$ and $m_2$ sets in $\mathcal S _2$ where $m_1 + m_2 = m$. Then the number of nonempty cells in the Venn diagram of these $m$ sets is at most

$$\begin{aligned} \pi ^*_{\mathcal{S }_{1}}(m_1)\pi ^*_{\mathcal{S }_{2}}(m_2) \le \pi ^*_{\mathcal{S }_{1}}(m)\pi ^*_{\mathcal{S }_{2}}(m).\square \end{aligned}$$

Lemma 2.4

Let $\Phi (X_1,X_2,{\dots },X_t)$ be a fixed set-theoretic expression (using the operations of union, intersection, and difference) with variables $X_1,{\dots },X_t$ standing for sets. Let $\mathcal S$ be a set system on a set $X$. Let $\mathcal T$ consist of all sets $\Phi (S_1,{\dots },S_t)$ for all possible choices $S_1,{\dots },S_t \in \mathcal S$. If $\pi ^*_\mathcal{S }(m) \le Cm^d$ for every $m$, then $\pi ^*_\mathcal{T }(m) \le Ct^dm^d$.

Proof

Each set in $\mathcal T$ is a disjoint union of some cells of the Venn diagram of some $t$ sets in $\mathcal S$. Therefore, given any $m$ sets in $\mathcal T$, each cell in the Venn diagram of these $m$ sets is a disjoint union of some cells in the Venn diagram of at most $tm$ sets of $\mathcal S$. Hence

$$\begin{aligned} \pi ^*_\mathcal T (m) \le \pi ^*_\mathcal S (tm) \le Ct^dm^d.\square \end{aligned}$$

3 Proof of Theorem 1.1

Let $K = (V,E)$ be a complete simple topological graph with $n+1$ vertices. Without loss of generality, we can assume $n$ is even. Notice that the edges of $K$ divide the plane into several cells (regions), one of which is unbounded. We can assume that there is a vertex $v_0 \in V$ such that $v_0$ lies on the boundary of the unbounded cell. Indeed, we can otherwise project $K$ onto a sphere, choose an arbitrary vertex $v_0$, and then project $K$ back to the plane such that $v_0$ lies on the boundary of the unbounded cell, and moreover two edges cross (are disjoint) in the new drawing if and only if they crossed (were disjoint) in the original drawing.

Given a subset $V^{\prime } \subset V$, we denote by $K[V^{\prime }]$ the topological subgraph induced by the vertex set $V^{\prime }$. Since we will be dealing with both combinatorial and topological graphs, the term edge will refer to an edge in a combinatorial graph and will be denoted by pairs of vertices $v_iv_j$. The term topological edge will refer to edges in the topological graph $K$, and will be denoted by $K[v_i,v_j]$ (i.e. the topological subgraph induced by vertices $v_i$ and $v_j$).

Consider the topological edges emanating out from $v_0$, and label their endpoints $v_1,{\ldots },v_n$ in counterclockwise order so that for $i < j$, the vertices $(v_0,v_i,v_j)$ appear in counterclockwise order along the simple closed curve $K[v_0,v_i,v_j]$. This is possible since $v_0$ lies on the unbounded cell and these three edges do not cross. For all pairs $i,j$, we will call the topological subgraph $K[v_0,v_i,v_j]$ a triangle in $K$. Note that each “triangle” is incident to $v_0$, and is a simple closed curve since $K$ is simple.

Set $X = \{v_1,{\ldots },v_n\}$, and now we will define the set system $(\mathcal{S }_1,X)$ as follows. For each pair $i,j$ that satisfies $1 \le i < j \le n$, we define the set $S_{i,j}$ to be the set of vertices in $X$ that lie in the interior of triangle $K[v_0,v_i,v_j]$. See Fig. 1(a) for a small example. Then set

$$\begin{aligned} \mathcal{S }_1 = \bigcup \limits _{1 \le i < j \le n} \left\{ S_{i,j}\right\} . \end{aligned}$$

Fig. 1

Sets $S_{3,6}\in \mathcal S _1$ and $S^{\prime }_{3,6}\in \mathcal S _2$

Lemma 3.1

Let $(\mathcal{S }_1,X)$ be the set system defined as above. Then $\pi ^*_\mathcal{S _1}(m) \le 5m^2$.

Proof

In order to obtain an upper bound on $\pi ^*_{\mathcal{S }_{1}}(m)$, we simply need to bound the maximum number of regions for which $m$ triangles in $K$ partitions the plane into. We proceed by induction on $m$. The base case when $m = 1$ is trivial. Now assume that the statement holds up to $m-1$. Notice that any set of $m-1$ triangles consists of at most $3(m-1)$ topological edges of $K$. Therefore, when we add the $m$th triangle $T$, each topological edge in $T$ creates at most $3(m-1)$ new crossing points (since $K$ is simple). Hence triangle $T$ creates at most $9(m-1)$ new regions in the arrangement. By the induction hypothesis, we have at most

$$\begin{aligned} 5(m-1)^2 + 9(m-1) \le 5m^2 \end{aligned}$$

cells created by the $m$ triangles.$\square$

Now we define the set system $(\mathcal{S }_2,X)$ as follows. For each pair $i,j$ that satisfies $1\le i < j \le n$, we define the set $S^{\prime }_{i,j} = \{v_k\in X : K[v_0,v_k] crosses K[v_i,v_j]\}$. See Fig. 1(b) for a small example. Then set

$$\begin{aligned} \mathcal{S }_2 = \bigcup \limits _{1\le i < j \le n}\left\{ S^{\prime }_{i,j}\right\} . \end{aligned}$$

Lemma 3.2

Let $\mathcal S = \mathcal{S }_1 \cup \mathcal{S }_2$ where $\mathcal{S }_1,\mathcal{S }_2$ are defined as above. Then $\pi ^*_\mathcal{S }(m) \le 120m^3$.

Proof

Let $i,j$ be fixed such that $i < j$. Notice that if $k$ is an integer that satisfies $k < i$ or $k > j$, then $v_k \in S^{\prime }_{i,j} \in \mathcal{S }_2$ if and only if $v_k \in S_{i,j} \in \mathcal{S }_1$. Moreover, if $k$ is an integer that satisfies $i < k < j$, then $v_k \in S^{\prime }_{i,j} \in \mathcal{S }_2$ if and only if $v_k \not \in S_{i,j} \in \mathcal{S }_1$. In what follows, we will apply Lemmas 2.3 and 2.4 in order to obtain the set system $\mathcal S = \mathcal{S }_1\cup \mathcal{S }_2$. This will ensure that the dual shatter function $\pi ^{*}_\mathcal{S }$ is well behaved.

Let $(\mathcal I ,X)$ be a set system such that

$$\begin{aligned} \mathcal{I } = \bigcup \limits _{1 \le i < j \le n} \left\{ I_{ij}\right\} , \end{aligned}$$

where $I_{ij} = \{v_k : i < k < j\}$. It is easy to see that $\pi ^*_\mathcal{I }(m) \le 2m+1\le 3m$, since this is equivalent to determining the number of cells created by $m$ intervals on the real line. Let $\mathcal{T }_1$ be the set system defined as $\mathcal{T }_1 = \mathcal{S }_1\cup \mathcal I \cup \{\emptyset \}$. By Lemmas 2.3 and 3.1, we have $\pi ^*_\mathcal{T _1}(m) \le 15m^3$. Notice that each set $S^{\prime }_{ij} \in \mathcal{S }_2$ can be expressed as

$$\begin{aligned} S^{\prime }_{ij} = (S_{ij} \setminus I_{ij}) \cup (I_{ij}\setminus S_{ij}), \end{aligned}$$

where $S_{ij} \in \mathcal{S }_1$ and $I_{ij} \in \mathcal I$ are defined above. Therefore, let $\Phi (X_1,X_2)$ be the set-theoretic expression defined as

$$\begin{aligned} \Phi (X_1,X_2) = (X_1\setminus X_2) \cup (X_2\setminus X_1), \end{aligned}$$

and let $\mathcal{T }_2$ consist of all sets $\Phi (X_1,X_2)$ for all possible choices $X_1,X_2 \in \mathcal{T }_1$. Hence $\mathcal S = \mathcal{S }_1\cup \mathcal{S }_2 \subset \mathcal{T }_2$. By Lemma 2.4, we have

$$\begin{aligned} \pi ^*_\mathcal{S }(m) \le \pi ^*_{\mathcal{T }_2}(m)\le \pi ^*_{\mathcal{T }_1}(2m) \le 15(2m)^3 = 120m^3.\square \end{aligned}$$

By setting $\mathcal S = \mathcal{S }_1\cup \mathcal{S }_2$, we know that $\pi ^*_\mathcal{S }(m) \le 120m^3$. Therefore we can apply Lemma 2.2 to $(\mathcal S ,X)$ and find a perfect matching $M$ on $X$ of which stabbing number is at most $Cn^{2/3}$, where $C$ is an absolute constant. In other words, each set in $S \in \mathcal S$ stabs at most $Cn^{2/3}$ members in $M$.

Now let $G = (V,E)$ be an $(n/2)$-vertex graph, where $V(G) = M$, and two vertices $v_{i}v_j, v_kv_l$ in $G$ (edges in $M$) are adjacent if and only if

• 1. $S_{i,j} \in \mathcal{S }_{1}$ stabs $v_kv_l$, or

• 2. $S^{\prime }_{i,j} \in \mathcal{S }_2$ stabs $v_kv_l$, or

• 3. $S_{k,l} \in \mathcal{S }_1$ stabs $v_iv_j$, or

• 4. $S^{\prime }_{k,l} \in \mathcal{S }_2$ stabs $v_iv_j$.

As $M$ has a stabbing number at most $Cn^{2/3}$, the two sets corresponding to each vertex in $G$ stab (in total) at most $2\cdot Cn^{2/3}$ other edges in $M$. A simple counting argument shows that $G$ contains at most $Cn^{5/3}$ edges. Therefore, we can use the following well-known theorem of Turán to find a large independent set in $M$.

Theorem 3.3

Every graph with $n$ vertices and $e$ edges contains an independent set of size at least $n^2/(2e + n)$.

In particular, the graph $G$ defined above contains an independent set of size $\varOmega (n^{1/3})$. Let $M^{\prime }\subset M$ be the edges corresponding to this independent set of size $\varOmega (n^{1/3})$. Now we claim that the corresponding topological edges in $K$ are pairwise disjoint. Indeed, let $e_1,e_2 \in M^{\prime }$ be such that $e_1 = v_iv_j$ and $e_2 = v_kv_l$. As the set $S_{i,j} \in \mathcal{S }_1$ does not stab $v_kv_l$, both vertices $v_k,v_l$ must either lie inside or outside of triangle $K[v_0,v_i,v_j]$. See Fig. 2.

Fig. 2

Cases 1 and 2

Case 1. Suppose that $v_k,v_l$ lie outside of triangle $K[v_0,v_i,v_j]$. For the sake of contradiction, suppose that the topological edges $K[v_i,v_j]$ and $K[v_k,v_l]$ cross. By a simple parity argument, $K[v_k,v_l]$ must cross either $K[v_0,v_i]$ or $K[v_0,v_j]$, but not both. However, this implies that the set $S^{\prime }_{k,l}\in \mathcal S _2$ stabs $v_iv_j$ which is a contradiction. Therefore, $K[v_i,v_j]$ and $K[v_k,v_l]$ must be disjoint.

Case 2. If $v_k,v_l$ lie inside of triangle $K[v_0,v_i,v_j]$, then by the same parity argument as above, $K[v_i,v_j]$ and $K[v_k,v_l]$ must be disjoint.

4 Concluding Remarks

 

• 1. Remarks on algorithms. As the matching in Lemma 2.2 and the independent set in Theorem 3.3 can be found in polynomial time (see [2] and [5]), the proof above gives a polynomial time algorithm for finding $\varOmega (n^{1/3})$ pairwise disjoint edges in a complete $n$-vertex simple topological graph.

• 2. We proved that every complete $n$-vertex simple topological graph has at least $\varOmega (n^{1/3})$ pairwise disjoint edges. It would be interesting to see if a polynomial bound holds for dense simple topological graphs.

• 3. We proved that the dual shatter function $\pi ^{*}_\mathcal{F }(m) = O(m^3)$. Recently Tóth [18] gave a construction showing that this bound is tight.

• 4. To our knowledge, there are no constructions of a complete $n$-vertex simple topological graph with sublinear number of pairwise disjoint edges. However, let us remark that Valtr [4] gave a construction of a complete $n$-vertex simple topological graph, such that every edge crosses at least $\varOmega (n^{3/2})$ other edges.