On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens

Abstract

A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. When allowing empty lenses (a face in the arrangement induced by two edges that is bounded by a 2-cycle), two independent edges may cross arbitrarily many times in a star-simple drawing. We consider star-simple drawings of $K_n$ with no empty lens. In this setting we prove an upper bound of $3((n-4)!)$ on the maximum number of crossings between any pair of edges. It follows that the total number of crossings is finite and upper bounded by n!.

This research started at the 3rd Workshop within the collaborative DACH project Arrangements and Drawings, August 19–23, 2019, in Wergenstein (GR), Switzerland, supported by the German Research Foundation (DFG), the Austrian Science Fund (FWF), and the Swiss National Science Foundation (SNSF). We thank the participants for stimulating discussions. S.F. is supported by DFG Project FE 340/12-1. M.H. is supported by SNSF Project 200021E-171681. K.K. is supported by DFG Project MU 3501/3-1 and within the Research Training Group GRK 2434 Facets of Complexity. I.P. was supported by FWF project I 3340-N35.

1 Introduction

A topological drawing of a graph G is a drawing in the plane where vertices are represented by pairwise distinct points, and edges are represented by Jordan arcs with their vertices as endpoints. Additionally, edges do not contain any other vertices, every common point of two edges is either a proper crossing or a common endpoint, and no three edges cross at a single point. A simple drawing is a topological drawing in which adjacent edges do not cross, and independent edges cross at most once.

We study a broader class of topological drawings, which are called star-simple drawings, where adjacent edges do not cross, but independent edges may cross any number of times; see Fig. 1 for illustration. In such a drawing, for every vertex v the induced substar centered at v is simple, that is, the drawing restricted to the edges incident to v forms a plane drawing. In the literature (e.g., [1, 2]) these drawings also appear under the name semi-simple, but we prefer star-simple because the name is much more descriptive.

Fig. 1.

Topological drawings of $K_6$ and a (nonempty) lens (shaded in (b)).

In contrast to simple drawings, star-simple drawings can have regions or cells whose boundary consists of two continuous pieces of (two) edges. We call such a region a lens; see Fig. 1b. A lens is empty if it has no vertex in its interior. If empty lenses are allowed, the number of crossings in star-simple drawings of graphs with at least two edges is unbounded (twisting), as illustrated in Fig. 2a. We restrict our attention to star-simple drawings with no empty lens. This restriction is—in general—not sufficient to guarantee a bounded number of crossings (spiraling), as illustrated in Fig. 2b. However, we will show that star-simple drawings of the complete graph $K_n$ with no empty lens have a bounded number of crossings.

Fig. 2.

Constructions to achieve an unbounded number of crossings.

Empty lenses also play a role in the context of the crossing lemma for multigraphs [5]. This is because a group of arbitrarily many parallel edges can be drawn without a single crossing. Hence, for general multigraphs there is no hope to get a lower bound on the number of crossings as a function of the number of edges. However, if we forbid empty lenses, we cannot draw arbitrarily many parallel edges.

Kynčl [3, Section 5], “Picture hanging without crossings”] proposed a construction of two edges in a graph on n vertices with an exponential number ($2^{n-4}$) of crossings and no empty lens; see Fig. 3. This configuration can be completed to a star-simple drawing of $K_n$, cf. [6]. For $n=6$ it is possible to have one more crossing while maintaining the property that the drawing can be completed to a star-simple drawing of $K_6$; see Fig. 4. Repeated application of the doubling construction of Fig. 3 leads to two edges with $2^{n-4}+2^{n-6}$ crossings in a graph on n vertices. This configuration can be completed to a star-simple drawing of $K_n$. We suspect that this is the maximum number of crossings of two edges in a star-simple drawing of $K_n$.

Fig. 3.

The doubling construction yields an exponential number of crossings.

Fig. 4.

Two edges with $2^{n-4}+2^{n-6}$ crossings in a star-simple drawing of $K_n$, for $n=6$.

2 Crossing Patterns

In this section we study the induced drawing $D(e,e')$ of two independent edges e and $e'$ in a star-simple drawing D of the complete graph. We start by observing that the endpoints of e and $e'$ must lie in the same region of $D(e,e')$. This fact was also used in earlier work by Aichholzer et al. [1] and by Kynčl [4].

Lemma 1

The four vertices incident to e and $e'$ belong to the same region of $D(e,e')$.

Proof

Assuming that the two edges cross at least two times, the drawing $D(e,e')$ has at least two regions. Otherwise, the statement is trivial. If the four vertices do not belong to the same region of $D(e,e')$, then there is a vertex u of e and a vertex v of $e'$ that belong to different regions. Now consider the edge uv in the drawing D of the complete graph. This edge has ends in different regions of $D(e,e')$, whence it has a crossing with either e or $e'$. This, however, makes a crossing in the star of u or v. This contradicts the assumption that D is a star-simple drawing.

Lemma 1 implies that the deadlock configurations as shown in Fig. 5a do not occur in star-simple drawings of complete graphs. Formally, a deadlock is a pair $e,e'$ of edges such that not all incident vertices lie in the same region of the drawing $D(e,e')$.

Now suppose that D is a star-simple drawing of a complete graph with no empty lens. In this case we can argue that e and $e'$ do not form a configuration as the black edge e and the red edge $e'$ in Fig. 5b. Indeed, that configuration has an interior lens L and by assumption this lens is non-empty, i.e., L contains a vertex x. Let e and $e'$ be the black and the red edge in Fig. 5b, respectively, and let u be a vertex of e. The edge xu (the green edge in the figure) has no crossing with e, hence it follows the “tunnel” of the black edge. This yields a deadlock configuration of the edges xu and $e'$. Note that if in Fig. 5b instead of drawing the green edge xu we connect x with an edge f to one of the vertices of the red edge $e'$ such that f and the red edge have no crossing, then f and the black edge e form a deadlock.

Fig. 5.

Constructions to achieve an unbounded number of crossings.

We use this intuition to formally define a spiral. Two edges $e,e'$ form a spiral if they form a lens L such that if we place a vertex x in L and draw a curve $\gamma$ connecting x to a vertex u of e so that $\gamma$ does not cross e, then $\gamma$ and $e'$ form a deadlock. The discussion above proves the following lemma:

Lemma 2

A star-simple drawing of a complete graph with no empty lens has no pair e, $e'$ of edges that form a spiral.

3 Crossings of Pairs of Edges

In this section we derive an upper bound for the number of crossings of two edges in a star-simple drawing of $K_n$ with no empty lens.

Theorem 1

Consider a star-simple drawing of $K_n$ with no empty lens. If C(k) is the maximum number of crossings of a pair of edges that (a) form no deadlock and no spiral and such that (b) all lenses formed by the two edges can be hit by k points, then $C(k) \le \mathrm {e}\cdot k!$, where $\mathrm {e}\approx 2.718$ is Euler’s number.

Proof

Due to Lemma 1 we can assume that all four vertices of e and $e'$ are on the outer face of the drawing $D(e,e')$. We think of $e'$ as being drawn red and horizontally and of e as being a black meander edge. Let $p_1,\ldots ,p_k$ be points hitting all the lenses of the drawing $D(e,e')$. Let u be one of the endpoints of e. For each $i=1,\ldots ,k$ we draw an edge $e_i$ connecting $p_i$ to u such that $e_i$ has no crossing with e and, subject to this, the number of crossings with $e'$ is minimized. Figure 6 shows an example.

Note that we do not claim that all these edges $e_1,\ldots ,e_k$ together with e and $e'$ can be extended to a star-simple drawing of a complete graph. Therefore, we cannot use Lemma 2 directly but state the assumption (a) instead.

Fig. 6.

The drawing $D(e,e')$ and an edge $e_i$ connecting $p_i$ to u.

We claim the following three properties:

• (P1) The edges $e_i$ and $e'$ form no deadlock and no spiral.

• (P2) All lenses of $e_i$ and $e'$ are hit by the $k-1$ points $p_1,\ldots ,p_{i-1},p_{i+1},\ldots ,p_k.$

• (P3) Between any two crossings of e and $e'$ from left to right, i.e., in the order along $e'$, there is at least one crossing of $e'$ with one of the edges $e_i$.

Before proving the properties, we show that they imply the statement of the theorem by induction on k. The base case $1=C(0) \le \mathrm {e}\cdot 0! = \mathrm {e}$ is obvious. From (P1) and (P2) we see that the number $X_i$ of crossings of $e_i$ and $e'$ is upper bounded by $C(k-1)$. From (P3) we obtain that $C(k) \le 1+ \sum _i X_i$. Combining these we get

For the proof of the three claims we need some notation. Let $\xi _1,\xi _2,\ldots ,\xi _N$ be the crossings of e and $e'$ indexed according to the left to right order along the horizontal edge $e'$. Let $g_i$ and $h_i$ be the pieces of $e'$ and e, respectively, between crossings $\xi _i$ and $\xi _{i+1}$. The bounded region enclosed by $g_i \cup h_i$ is the bag $B_i$ and $g_i$ is the gap of the bag. In the drawing $D(e,e')$ the bags $B_i$ where $h_i$ is a crossing free piece of e are exactly the inclusion-wise minimal lenses formed by e and $e'$. From now on when referring to a lens we always mean such a minimal lens. Indeed if there is no empty minimal lens, then there is no empty lens. The following observation is crucial.

Observation 2

For two bags $B_i$ and $B_j$ the open interiors are either disjoint or one is contained in the other.

Proof

Every bag is bounded by a closed Jordan curve, and the boundaries of two distinct bags do not cross (at most they may touch at a single point that is one of $\xi _1,\xi _2,\ldots ,\xi _N$).

Observation 2 implies that the containment order on the bags is a downwards branching forest. The minimal elements in the containment order are the lenses. Consider a lens L and the point $p_i$ inside L. Since the vertex u of e is in the outer face of $D(e,e')$, the edge $e_i$ has to leave each bag that contains L. Furthermore, by definition $e_i$ does not cross e and therefore it has to leave a bag B containing L through the gap g of B. We now reformulate and prove the third claim (P3).

• (P3’) For each pair $\xi _i,\xi _{i+1}$ of consecutive crossings on $e'$ there is a lens L and a point $p_j\in L$ such that $e_j$ crosses $e'$ between $\xi _i$ and $\xi _{i+1}$.

Proof sketch for (P3’). The pair $\xi _i,\xi _{i+1}$ is associated with the bag $B_i$. In the containment order of bags a minimal bag below $B_i$ is a lens, let L be any of the minimal elements below $B_i$. By assumption, L contains a point $p_j$. Since $L \subseteq B_i$, we have that also $p_j \in B_i$. Thus, it follows that $e_j$ has a crossing with the gap $g_i$, i.e., $e_j$ has a crossing with $e'$ between $\xi _i$ and $\xi _{i+1}$.

Proof sketch for (P1). We have to show that $e_i$ and $e'$ form no deadlock and no spiral. The minimality condition in the definition of $e_i$ implies that if $L=B_{i_1}\subset B_{i_2}\subset \ldots \subset B_{i_t}$ is the maximal chain of bags with minimal element L, then $e_i$ crosses the gaps of these bags in the given order and has no further crossings with $e'$. If $\gamma$ is a curve from L to u that avoids e, then in the ordered sequence of gaps crossed by $\gamma$ we find a subsequence that is identical to the ordered sequence of gaps crossed by $e_i$. Since e and $e'$ form no spiral, there is such a curve $\gamma$ that forms no deadlock with $e'$. Therefore, $e_i$ forms no deadlock with $e'$, either.

Now assume that $e_i$ and $e'$ form a spiral. Let B be the largest bag containing $p_i$. Think of B as a drawing of $e_i$ with a broad pen, which may also have some extra branches that have no correspondence in $e_i$, see Fig. 7. The formalization of this picture is that for every bag $\beta$ formed by $e_i$ with $e'$ there is a bag $B(\beta )$ formed by e and $e'$ with $B(\beta ) \subset \beta$. Now, if there is a lens $\lambda$ formed by $e_i$ with $e'$ such that every $e_i$-avoiding¹ curve to u is a deadlock with $e'$, then there is a lens $L(\lambda )$ formed by e and $e'$ with $L(\lambda ) \subset \lambda$ such that every e-avoiding curve from $L(\lambda )$ to u is also B-avoiding and hence $e_i$-avoiding. Thus, every such curve has a deadlock with $e'$, whence e and $e'$ form a spiral, contradiction.    $\square$

Proof sketch for (P2). We know by P1 that $e_i$ and $e'$ form no deadlock. Therefore, by Lemma 1, the vertices of $e_i$ and $e'$ belong to the same region of $D(e_i,e')$. All crossings of $e_i$ with $e'$ correspond to bags of e and $e'$, therefore the vertices of e and $e'$ are in the outer face of $D(e_i,e')$. Together this shows that $p_i$ is also in the outer face of $D(e_i,e')$. Since every lens of $D(e_i,e')$ contains a lens of $D(e,e')$, it also contains one of the points hitting all lenses of $D(e,e')$. Hence, all lenses of $D(e_i,e')$ are hit by the $k-1$ points $p_1,\ldots ,p_{i-1},p_{i+1},\ldots ,p_k$.    $\square$

Fig. 7.

An edge $e_i$(green) that forms a spiral with $e'$. The bag B in gray and the lens $L(\lambda )$ marked with the vertex $p_j$(blue). (Color figure online)

4 Crossings in Complete Drawings

Accounting for the four endpoints of the two crossing edges we have $k\le n-4$ in Theorem 1. Therefore, we obtain that the number of crossings of a pair of edges in a star-simple drawing of $K_n$ without empty lens is upper bounded by $3(n-4)!$. This directly implies that the drawing of $K_n$ has at most n! crossings. This is the first finite upper bound on the number of crossings in star-simple drawings of the complete graph $K_n$. We know drawings of $K_n$ in this drawing mode that have an exponential number of crossings. Thus, it would be interesting to reduce the huge gap between the upper and the lower bound. Specifically, can a star-simple drawing of $K_n$ have two edges with more than $2^{n-4}+2^{n-6}$ crossings?