Characterizing and Recognizing Twistedness

Aichholzer, Oswin; García, Alfredo; Tejel, Javier; Vogtenhuber, Birgit; Weinberger, Alexandra

doi:10.4230/LIPIcs.GD.2025.25

Characterizing and Recognizing Twistedness

Oswin Aichholzer

Graz University of Technology, Austria Alfredo García

Departamento de Métodos Estadísticos and IUMA, University of Zaragoza, Spain Javier Tejel

Departamento de Métodos Estadísticos and IUMA, University of Zaragoza, Spain Birgit Vogtenhuber

Graz University of Technology, Austria Alexandra Weinberger

FernUniversität in Hagen, Germany

Abstract

In a simple drawing of a graph, any two edges intersect in at most one point (either a common endpoint or a proper crossing). A simple drawing is generalized twisted if it fulfills certain rather specific constraints on how the edges are drawn. An abstract rotation system of a graph assigns to each vertex a cyclic order of its incident edges. A realizable rotation system is one that admits a simple drawing such that at each vertex, the edges emanate in that cyclic order, and a generalized twisted rotation system can be realized as a generalized twisted drawing. Generalized twisted drawings have initially been introduced to obtain improved bounds on the size of plane substructures in any simple drawing of $K_{n}$ . They have since gained independent interest due to their surprising properties. However, the definition of generalized twisted drawings is very geometric and drawing-specific.

In this paper, we develop characterizations of generalized twisted drawings that enable a purely combinatorial view on these drawings and lead to efficient recognition algorithms. Concretely, we show that for any $n\geq 7$ , an abstract rotation system of $K_{n}$ is generalized twisted if and only if all subrotation systems induced by five vertices are generalized twisted. This implies a drawing-independent and concise characterization of generalized twistedness. Besides, the result yields a simple $O(n^{5})$ -time algorithm to decide whether an abstract rotation system is generalized twisted and sheds new light on the structural features of simple drawings. We further develop a characterization via the rotations of a pair of vertices in a drawing, which we then use to derive an $O(n^{2})$ -time algorithm to decide whether a realizable rotation system is generalized twisted.

Keywords and phrases:

generalized twisted drawings, simple drawings, rotation systems, recognition, combinatorial characterization, efficient algorithms

Funding:

Javier Tejel: Partially supported by project E41-23R, funded by Gobierno de Aragón, and project PID2023-150725NB-I00, funded by MICIU/AEI/10.13039/501100011033.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Combinatorics ; Mathematics of computing

\rightarrow

Graph theory

Editors:

Vida Dujmović and Fabrizio Montecchiani

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Figure 1: Two realizations of the generalized twisted rotation system of

K_{5}

. Left: Generalized twisted drawing where the origin

O

and ray

r

are depicted. Right: The classical twisted drawing.

Simple drawings are drawings of graphs in which the vertices are drawn as distinct points in the plane, the edges are drawn as Jordan arcs connecting their end-vertices without passing through other vertices, and each pair of edges share at most one point (a proper crossing or a common endpoint). We consider two simple drawings the same if they are strongly isomorphic, that is, if there is a homeomorphism of the plane transforming one drawing into the other. In this work we focus on simple drawings of $K_{n}$ . Unless explicitly stated otherwise, all considered drawings are of $K_{n}$ and simple. A simple drawing $D$ is generalized twisted if it is strongly isomorphic to a simple drawing in which there is a point $O$ such that each ray emanating from $O$ crosses each edge of $D$ at most once and there exists a ray $r$ emanating from $O$ such that all edges of $D$ cross $r$ . For an example see Figure 1(left), which has been reproduced from [15].

Generalized twisted drawings have been used to find plane substructures in all simple drawings of $K_{n}$ : The currently best bounds on the size of the largest plane matching and longest plane cycle and path in any simple drawing of $K_{n}$ have been obtained via generalized twisted drawings [5]. Moreover, generalized twisted drawings are the largest class of drawings for which it has been shown that each drawing has exactly $2n-4$ empty triangles [14, 15], which is conjectured to be the minimum over all simple drawings [6]. There are several more interesting properties of generalized twisted drawings that have been shown already [4, 5, 15]. For example, all generalized twisted drawings contain plane cycles of length at least $n-1$ [5].

Despite the usefulness of generalized twisted drawings, their definition is very geometrical and drawing-specific. In this paper, we obtain combinatorial characterizations that no longer depend on the specific drawing, which ease the work with them and also allow for efficient recognition. Note that ad hoc it is not clear that such a combinatorial characterization needs to exist. The study of special classes of simple drawings [3, 11, 12, 13] and their combinatorial characterizations [8, 9, 10, 22, 23] has a strong tradition in the research of simple drawings and contributes significantly to the understanding simple drawings in general.

A widely used combinatorial abstraction of drawings are rotation systems. The rotation of a vertex in a drawing is the cyclic order of its incident edges. The rotation system of a simple drawing is the collection of the rotations of all vertices. Rotation systems are especially useful for describing simple drawings of complete graphs, since two simple drawings of $K_{n}$ have the same crossing edge pairs if and only if they have the same or inverse rotation system [7, 16, 17, 19]. Rotation systems of graphs can also be considered without a concrete drawing. An abstract rotation system of a graph $G$ gives, for every vertex of $G$ , a cyclic order of its adjacent vertices. An abstract rotation system is called realizable if there exists a simple drawing with that rotation system. For abstract rotation systems of complete graphs, realizability can be checked in polynomial time. Specifically, an abstract rotation system of $K_{n}$ is realizable if and only if every subrotation system induced by five vertices is realizable. This follows from a combinatorial characterization via subrotation systems of size six [20, Theorem 1.1.] together with a complete enumeration of all realizable rotation systems of $K_{n}$ for $n\leq 9$ [2].

In this work, we use rotation systems to characterize generalized twisted drawings. An abstract rotation system of a graph is generalized twisted if there is a generalized twisted drawing realizing this rotation system. As our first main result, we show that generalized twisted rotation systems of $K_{n}$ can also be characterized via subrotation systems of size five. The main benefit of this result is to have a drawing-independent (and concise) characterization of generalized twistedness. The substructures to be considered are of constant size and straightforward to be checked, which improves the insight into generalized twisted drawings.

Theorem 1.

Let $R$ be an abstract rotation system of $K_{n}$ with $n\geq 7$ . Then $R$ is generalized twisted if and only if every subrotation system induced by five vertices is generalized twisted.

This characterization of generalized twisted rotation systems nicely complements the characterization of all realizable simple drawings in general, which can also be done by considering subrotation systems of size five [2, 20]. Per se, such characterizations of bounded complexity do not always need to exist. For example, if the combinatorics of an (abstract) set of points is given by their triple orientations – so-called abstract order types – no simple characterization to decide their realizability as a point set in the plane can exist, as this decision problem is known to be $\exists\mathbb{R}$ -complete; see the recent survey [24] for details.

The main part of Theorem 1 is the “if” part. The “only-if” part follows from the fact that subdrawings of generalized twisted drawings are generalized twisted by definition. As mentioned in the article introducing generalized twisted drawings [4], there is exactly one generalized twisted rotation system $T_{5}$ of $K_{5}$ , namely, the one of the twisted drawing [18, 21] of $K_{5}$ , which gave rise to the name “generalized twisted”; see Figure 1(right) for an illustration as in [21]. We remark that Theorem 1 cannot be extended to $n\leq 6$ . Figure 2 depicts a drawing from [4], where it has been shown that the rotation system of this drawing is not generalized twisted, although all its subrotation systems are (generalized) twisted.

Figure 2: A simple drawing of

K_{6}

whose rotation system is not generalized twisted, even though all subrotation systems on five vertices are.

Figure 3: Illustration of Theorem 2: Possible rotations of

v_{1}

and

v_{2}

. The vertices of partition set

A

are drawn as red disks and the vertices of partition set

B

as blue squares.

Our second main result is a characterization of generalized twisted drawings via rotation systems and crossings as stated in Theorem 2 below and depicted on an example in Figure 3.

Figure 4: A realization of the generalized twisted rotation system

T_{5}

of

K_{5}

. The pairs of antipodal vi-cells are marked with red squares and blue crosses, the maximum crossing edge is bold, and empty triangles are indicated by (brown) circular arcs.

Theorem 2.

Let $R$ be the rotation system of a simple drawing $D$ of $K_{n}$ and let $V$ be the set of vertices of $D$ . Then $R$ is generalized twisted if and only if there exist two vertices $v_{1}$ and $v_{2}$ in $V$ and a bipartition $A\cup B$ of the vertices in $V\setminus\{v_{1},v_{2}\}$ , where some of $A$ or $B$ can be empty, such that:

(i)

For every pair of vertices $a$ and $a^{\prime}$ in $A$ , the edge $aa^{\prime}$ crosses $v_{1}v_{2}$ .
(ii)

For every pair of vertices $b$ and $b^{\prime}$ in $B$ , the edge $bb^{\prime}$ crosses $v_{1}v_{2}$ .
(iii)

For every vertex $a\in A$ and every vertex $b\in B$ , the edge $a b$ does not cross $v_{1}v_{2}$ .
(iv)

Beginning at $v_{2}$ , in the rotation of $v_{1}$ , all vertices in $B$ appear before all vertices in $A$ .
(v)

Beginning at $v_{1}$ , in the rotation of $v_{2}$ , all vertices in $B$ appear before all vertices in $A$ .

The main implication of Theorem 2 is that it leads to fast algorithms for recognizing generalized twisted rotation systems. If it is already known that a rotation system is realizable (which needs $O(n^{5})$ time to be checked [2, 20]), we can even use it to obtain a quadratic time recognition algorithm.

Theorem 3.

Let $R$ be an abstract rotation system of $K_{n}$ . Then it can be decided in $O(n^{5})$ time whether $R$ is generalized twisted. If $R$ is known to be realizable, then deciding whether it is also generalized twisted can be done in $O(n^{2})$ time.

Outline.

We start by introducing some notation and showing first properties in Section 2. Sections 3 and 4 are devoted to proving the two characterizations, Theorem 1 and Theorem 2, respectively. In Section 5, we prove Theorem 3 by providing the algorithms. We conclude in Section 6 with some open questions.

2 Preliminaries

Given a simple drawing $D$ , the star at v, denoted by $S(v)$ , is the set of edges incident to $v$ in $D$ . For a set $V$ of vertices of $D$ , we denote by $D\setminus V$ the drawing $D$ without the vertices in $V$ and without all edges incident to a vertex in $V$ . A triangle $\Delta$ in $D$ is the simple closed curve formed by three vertices and the three edges connecting them. Every triangle partitions the plane and hence $D$ into two regions which we call the sides of $\Delta$ . The whole drawing $D$ partitions the plane into regions called cells.

In our proofs, we heavily rely on antipodal vi-cells, empty star triangles, and maximum crossing edges, all of which we describe in the following paragraphs.

Antipodal vi-cells.

A cell that is incident to a vertex (that is, has the vertex on its boundary) is called vertex-incident cell or vi-cell. We observe that if there is a vi-cell at $v$ containing the initial parts of $v u$ and $v w$ in one drawing of a rotation system, then $v u$ and $v w$ are neighboring in the rotation of $v$ . Since the latter property depends only on the rotation system of the drawing, there is a vi-cell at $v$ in every drawing of this rotation system with initial parts of $v u$ and $v w$ on the boundary. Note that the remainder of the boundary of the vi-cell is not necessarily identical across different drawings of the rotation system. Two cells are antipodal if for every triangle, the two cells are on different sides. A vi-cell that is antipodal to some other vi-cell is called a via-cell. (In Figure 4, the two pairs of via-cells are marked.) Since the set of crossing edge pairs determines the rotation system and vice versa [17, 19], also the existence of via-cells is a property of the rotation system. A vertex incident to a via-cell is called a via-vertex.

We will need the following known theorem [4, Theorem 15]¹¹1The original formulation uses drawings and weak isomorphism. Our formulation is equivalent due to the equivalence of rotation systems and weak isomorphism [17, 19]..

Theorem 4 ([4]).

The rotation system of a simple drawing $D$ of $K_{n}$ is generalized twisted if and only if $D$ contains a pair of antipodal vi-cells.

Note that the characterization in Theorem 4 implies that a rotation system is generalized twisted if and only if all its realizations as simple drawings contain a pair of antipodal vi-cells.

Empty star triangles.

A triangle $\Delta$ with vertices $x, y$ and $z$ is a star triangle at $x$ if the star $S(x)$ does not cross the edge $y z$ ; it is empty if one side of $\Delta$ contains no vertices of $D\setminus\Delta$ (and hence the other side contains all of them). (In Figure 4, each circular arc between two edges at a vertex indicates that the triangle containing those two edges is an empty star triangle at that vertex.) We call two star triangles at $x$ adjacent if they are both incident to some edge $x y$ and span disjoint angles at $x$ . We will use the following results on empty star triangles in simple and generalized twisted drawings.

Lemma 5 ([6]).

Let $v$ be a vertex of a simple drawing $D$ of $K_{n}$ . Then $D$ contains at least two empty star triangles at $v$ . If $v x y$ is a star triangle at $v$ then it is empty if and only if the vertices $x$ and $y$ are consecutive in the rotation of $v$ .

Lemma 6 ([15]).

Let $D$ be a generalized twisted drawing of $K_{n}$ and let $v$ be a vertex of $D$ . Then there are exactly two empty star triangles at $v$ . If $(C_{1},C_{2})$ is a pair of antipodal vi-cells in $D$ , then one of the two empty star triangles at $v$ contains $C_{1}$ on the empty side and the other triangle contains $C_{2}$ on the empty side.

Maximum crossing edges.

An edge $v_{1}v_{2}$ is maximum crossing if $v_{1}v_{2}$ crosses every edge not in $S(v_{1})\cup S(v_{2})$ . (For example, the bold edge in Figure 4 is maximum crossing.) Any simple drawing has at most one maximum crossing edge, as the following lemma states.

Lemma 7.

Any simple drawing of $K_{n}$ with $n\geq 5$ has at most one maximum crossing edge.

Lemma 7 holds for $n=5$ because none of the five simple drawings of $K_{5}$ (up to strong isomorphism) [6] contains more than one maximum crossing edge. Using this fact, the lemma can be proven for $n>5$ by contradiction, assuming that a simple drawing contains several maximum crossing edges.

We next observe in Lemma 8 that maximum crossing edges imply generalized twisted rotation systems. Figure 5 illustrates the lemma.

Lemma 8.

Let $D$ be a simple drawing of $K_{n}$ that has a maximum crossing edge, $v_{1}v_{2}$ . Let $C_{1}$ and $C^{\prime}_{1}$ be the two cells incident to $v_{1}$ along the edge $v_{1}v_{2}$ and let $C_{2}$ and $C^{\prime}_{2}$ be the two cells incident to $v_{2}$ along the edge $v_{1}v_{2}$ such that when going along the edge from $v_{1}$ to $v_{2}$ , the cell $C_{1}$ is on the other side of $v_{1}v_{2}$ than the cell $C_{2}$ (and consequently $C^{\prime}_{1}$ is on the other side of $v_{1}v_{2}$ than $C^{\prime}_{2}$ ). Then $D$ is generalized twisted and $(C_{1},C_{2})$ and $(C^{\prime}_{1},C^{\prime}_{2})$ are two pairs of antipodal vi-cells.

Figure 5: A maximum crossing edge

v_{1}v_{2}

(in bold) and the two pairs,

(C_{1},C_{2})

and

(C^{\prime}_{1},C^{\prime}_{2})

, of antipodal vi-cells.

Lemma 8 can be shown by taking an arbitrary triangle of the generalized twisted drawing and considering where the cells adjacent to the edge $v_{1}v_{2}$ and its endpoints must lie with respect to this triangle in order to allow the edge $v_{1}v_{2}$ to cross all non-adjacent edges.

3 Characterization via subrotation systems induced by five vertices

In this section, we prove Theorem 1 by induction. To this end, we use the following theorem, whose proof we sketch in Section 3.1.

Theorem 9.

Let $R$ be an abstract rotation system of $K_{n}$ with $n\geq 12$ such that every induced subrotation system on at most $n-1$ vertices is generalized twisted. Then $R$ is generalized twisted.

Proof of Theorem 1.

By definition, if $R$ is generalized twisted, then any subrotation system induced by five vertices is generalized twisted. We prove the converse: if every subrotation system induced by five vertices is generalized twisted, then $R$ is generalized twisted.

For $7\leq n\leq 11$ , the theorem is verified by computer. Following the lines of [1, 5], we compute all generalized twisted rotation systems of $K_{n}$ for $n$ up to $15$ in the following way. First, we use the method of [2] to generate all realizable rotation systems, but discard those with subrotation systems induced by five vertices different to $T_{5}$ , thus computing all candidate rotation systems for generalized twisted drawings. In each candidate rotation system, we then search for a pair of antipodal vi-cells. By Theorem 4, this identifies all generalized twisted rotation systems. Any rotation system contradicting Theorem 1 does not have antipodal vi-cells. The computational results give only one rotation system of size $n=6$ (drawn in Figure 2) that is not generalized twisted.

For $n\geq 12$ , we use induction. Every induced subrotation system of $R$ on at most $n-1$ vertices is generalized twisted by induction. Thus, $R$ is generalized twisted by Theorem 9. $\hfill\blacktriangleleft$

3.1 Proof sketch of Theorem 9

Let $R$ be as in Theorem 9 and let $D$ be a realization of $R$ , which exists since any abstract rotation system of $K_{n}$ is realizable if all subrotation systems induced by five vertices are [2, 20]. Since each induced and proper subdrawing of $D$ has a generalized twisted rotation system, it also has a pair of antipodal vi-cells by Theorem 4. We use this to show that also $D$ has such a pair and thus, by Theorem 4, $R$ is generalized twisted. The idea is to locate antipodal vi-cells of $D$ using those in its induced subdrawings and empty triangles. The following lemma can be shown using Lemma 5 (for a lower bound) and Lemma 6 (for an upper bound).

Lemma 10.

Let $D$ be a drawing of $K_{n}$ with $n\geq 5$ such that every induced and proper subdrawing has a generalized twisted rotation system. Then at any vertex of $D$ , there are exactly two empty star triangles.

We separately consider the case where $D$ contains a vertex $u$ with two adjacent empty star triangles at $u$ and the case that there is no such vertex.

Case 1: Two adjacent empty star triangles at a vertex $𝒖$ .

This is the easy case. We first show the following lemma on generalized twisted rotation systems of $K_{n}$ . Its proof is based on considering two adjacent empty star triangles at a vertex $v_{1}$ and analyzing all possibilities of how to extend these triangles to a drawing of $T_{5}$ and then to a drawing of $K_{6}$ with a generalized twisted rotation system.

Lemma 11.

Let $v_{1}$ and $v_{2}$ be two vertices of a simple drawing of $K_{n}$ with generalized twisted rotation system such that the two empty star triangles at vertex $v_{1}$ are sharing the edge $v_{1}v_{2}$ . Then the following properties hold.

1.

The edge $v_{1}v_{2}$ is maximum crossing.
2.

The two empty star triangles at $v_{1}$ are also empty star triangles at $v_{2}$ .
3.

For each of the two empty star triangles at $v_{1}$ , the vertices $v_{1}$ and $v_{2}$ are adjacent in the rotation of the third vertex of the triangle in such a way that all edges emanate from the third vertex in the empty side of the triangle.

Then we consider the drawing $D$ and the two adjacent empty star triangles at $u$ in $D$ . As every proper subdrawing of $D$ has a generalized twisted rotation system, Lemma 11 implies that the edge shared by the two adjacent empty star triangles at $u$ is maximum crossing. Thus, the rotation system of $D$ is generalized twisted by Lemma 8.

Case 2: No vertex with two adjacent empty star triangles.

This is the involved case. Let $v_{1}$ be an arbitrary vertex of $D$ and let $\Delta_{1}=v_{1}u_{1}u^{\prime}_{1}$ and $\Delta_{2}=v_{1}u_{2}u^{\prime}_{2}$ be the (nonadjacent) empty star triangles at $v_{1}$ . Our goal is to show that using via-cells of some induced and proper subdrawings of $D$ , we can find a pair $(C_{1},C_{2})$ of vi-cells in $D$ such that $C_{1}$ lies in $\Delta_{1}$ and $C_{2}$ in $\Delta_{2}$ , and prove that $C_{1}$ and $C_{2}$ are antipodal.

Let $V_{0}$ be the set of vertices of $\Delta_{1}$ and $\Delta_{2}$ , and let $D_{0}$ be the subdrawing induced by $V_{0}$ . Since the rotation system of $D_{0}$ is generalized twisted and has only five vertices, we have all the information about that drawing. This includes in particular the maximum crossing edge of $D_{0}$ , which we denote by $m$ , the two pairs of antipodal vi-cells of $D_{0}$ , and the empty star triangles. As $\Delta_{1}$ and $\Delta_{2}$ are not adjacent, $v_{1}$ is one of the vertices $\{a,b,d\}$ in Figure 6.

Figure 6: A drawing of the unique generalized twisted rotation system

T_{5}

of

K_{5}

, which is strongly isomorphic to the one in Figure 1, but redrawn to make empty star triangles and the relevant cells more visible. Empty star triangles at a vertex are marked with brown arcs at the angle that spans the triangle. The two pairs of antipodal vi-cells are marked with red squares and blue crosses.

Figure 7: Three drawings realizing

T_{5}

in such a way that

v_{1}

is drawn in the center. The underlying unlabeled drawings are strongly isomorphic. The labels correspond to those in Figure 6 with

v_{1}=a

(left),

v_{1}=d

(middle), or

v_{1}=b

(right). The maximum crossing edge

m

is drawn bold, the two pairs of antipodal vi-cells are marked with red squares and blue crosses.

Observe that the vertices $a$ and $d$ behave analogously to each other while vertex $b$ behaves differently (see Figure 7). We argue via the triangles $\Delta_{1}$ and $\Delta_{2}$ separately but simultaneously, because we will consider only one triangle but require that the other triangle has the same properties. We sketch the case where $v_{1}$ is $a$ or $d$ and focus mostly on $\Delta_{1}$ . The properties for $\Delta_{2}$ can be shown analogously and the case of $v_{1}$ behaving like $b$ then follows immediately.

For identifying all pairs of antipodal vi-cells in subdrawings of $D$ , we state in Lemma 12 properties of simple drawings with more than one such pair.

Lemma 12.

Let $D$ be a simple drawing of $K_{n}$ with different antipodal vi-cell pairs $(C_{1},C_{2})$ and $(C^{\prime}_{1},C^{\prime}_{2})$ . Then

1.

For one of the vertices on the boundary of a cell in $\{C_{1},C_{2},C^{\prime}_{1},C^{\prime}_{2}\}$ , there are two empty star triangles at that vertex that share an edge.
2.

There is a maximum crossing edge which is the shared edge of the two empty star triangles at one of the endpoints of the edge.
3.

The via-cells are adjacent to the maximum crossing edge (as described in Lemma 8).
4.

$D$ has only those two (and no more) pairs of antipodal vi-cells.

Proof Sketch.

The proof of (1) is by contradiction. Assuming that the two empty star triangles at any vertex on the boundary of a cell in $\{C_{1},C_{2},C^{\prime}_{1},C^{\prime}_{2}\}$ are not adjacent, we can find an induced subdrawing on 5 or 6 vertices that is not generalized twisted, a contradiction. (2) and (3) follow from Lemma 11, as by (1) there are two empty star triangles that are adjacent. (4) follows from the fact that if there is a third pair of antipodal vi-cells, then $D$ would contain two maximum crossing edges, contradicting Lemma 7. $\hfill\blacktriangleleft$

Let $V^{\prime}$ be a nonempty subset of $V\setminus V_{0}$ . By Lemma 12 and Lemma 6, one of the following holds for the subdrawing $D\setminus{V^{\prime}}$ of $D$ :

1.

$D\setminus{V^{\prime}}$ contains exactly one pair of antipodal vi-cells. One of those cells is in the empty side of triangle $\Delta_{1}$ and the other one is in the empty side of triangle $\Delta_{2}$ .
2.

$D\setminus{V^{\prime}}$ contains exactly two pairs of antipodal vi-cells. For each pair, one cell is in the empty side of $\Delta_{1}$ and the other one is in the empty side of $\Delta_{2}$ . Further, for each of $\Delta_{1}$ and $\Delta_{2}$ , the two vi-cells in its empty side are adjacent along the maximum crossed edge of $D\setminus{V^{\prime}}$ and incident to the endpoints of this edge.

The next lemma states the possibilities of how arbitrary antipodal vi-cell pairs of two subdrawings $D\!\setminus\!\{v\}$ and $D\!\setminus\!\{w\}$ of $D$ can be contained in all pairs of the subdrawing $D\!\setminus\!\{v,w\}$ . The proof uses observations on the containment of cells of a drawing $D^{\prime}$ in cells of its subdrawings and consequences of two cells being antipodal. We denote by $(C_{1}^{v_{1}v_{2}\ldots}\!,C_{2}^{v_{1}v_{2}\ldots})$ an antipodal vi-cell pair in the drawing $D\!\setminus\!\{v_{1},v_{2},\ldots\}$ .

Figure 8: The grid cells of

D

and

D\!\setminus\!{\{w\}}

inside triangle

\Delta_{1}

.

Lemma 13.

For any pair $(C_{1}^{v},C_{2}^{v})$ of antipodal vi-cells in $D\!\setminus\!\{v\}$ and any pair $(C_{1}^{w},C_{2}^{w})$ of antipodal vi-cells in $D\!\setminus\!\{w\}$ , then

1.

If $D\!\setminus\!\{v,w\}$ has only one antipodal vi-cell pair, $(C_{1}^{vw}\!,C_{2}^{vw})$ , then $(C_{1}^{v},C_{2}^{v})$ and $(C_{1}^{w},C_{2}^{w})$ both are contained in $(C_{1}^{vw},C_{2}^{vw})$ .
2.

If $D\!\setminus\!{\{v,w\}}$ has two antipodal vi-cell pairs $(C_{1}^{vw},C_{2}^{vw})$ and $({C_{1}^{\prime}}^{vw},{C_{2}^{\prime}}^{vw})$ , then either $(C_{1}^{v},C_{2}^{v})$ and $(C_{1}^{w},C_{2}^{w})$ both are contained in one of $(C_{1}^{vw},C_{2}^{vw})$ and $({C_{1}^{\prime}}^{vw},{C_{2}^{\prime}}^{vw})$ , or $(C_{1}^{v},C_{2}^{v})$ is contained in one of $(C_{1}^{vw},C_{2}^{vw})$ and $({C_{1}^{\prime}}^{vw},{C_{2}^{\prime}}^{vw})$ , and $(C_{1}^{w},C_{2}^{w})$ in the other.

We identify grid structures in the empty sides of $\Delta_{1}$ and $\Delta_{2}$ in $D$ that we will work with to locate candidates for antipodal vi-cells of $D$ . As $\Delta_{1}$ is an empty star triangle at $v_{1}$ and as $D$ is a simple drawing, no edge incident to $v_{1}$ can cross an edge of $\Delta_{1}$ . However, every generalized twisted drawing of $K_{4}$ contains a crossing [5]. Hence, for every vertex $v\notin\Delta_{1}$ , exactly one of $vu_{1}$ or $vu^{\prime}_{1}$ crosses $\Delta_{1}$ (on $v_{1}u^{\prime}_{1}$ or $v_{1}u_{1}$ , respectively). We denote this edge by $r_{v}$ . The set of edges $r_{v}$ for every $v$ form a grid in the empty side of $\Delta_{1}$ in $D$ . We denote the cells of this grid that have some vertex (of $\Delta_{1}$ ) on the boundary as grid cells; see Figure 8. Grid cells in $\Delta_{2}$ are defined analogously. Note that grid cells may consist of several cells of $D$ , as edges of $D$ can cross through $\Delta_{1}$ and/or $\Delta_{2}$ .

Next, we obtain an order on the grid cells of $\Delta_{1}$ (and analogously on $\Delta_{2})$ . Consider the dual graph of the grid cells (where the vertices are the grid cells and two vertices share an edge if the corresponding grid cells are adjacent). This dual graph is either a path or a path plus an isolated vertex (e.g. grid cell $9$ in Figure 8 left). We label the grid cells $G_{1},\ldots,G_{l}$ , along this dual path, beginning with the grid cell with vertex $u_{1}$ and adjacent to edge $u_{1}v_{1}$ , and finishing with the cell that has $v_{1}$ on its boundary; see Figure 8 left for an example. The distance between two grid cells $G_{i},G_{j}$ is the number of edges $r_{v}$ separating $G_{i}$ and $G_{j}$ . If edge $r_{v}$ is incident to both $G_{i}$ and $G_{i+1}$ , we say that $G_{i}$ and $G_{i+1}$ are glued along $r_{v}$ . We denote the two grid cells that are glued along the edge $m$ (which is the maximum crossed edge of $D_{0}$ ) by $G_{c}$ and $G_{c+1}$ (cells $4,5$ in Figure 8 left). We say that grid cell $G_{i}$ is placed before $m$ if $i\leq c$ ; and placed after $m$ otherwise.

When removing a vertex $v\in V\setminus V_{0}$ , we obtain a grid in $D\!\setminus\!{\{v\}}$ whose only difference to the grid in $D$ is that two grid cells of $D$ that are adjacent at the edge $r_{v}$ become one grid cell in $D\!\setminus\!{\{v\}}$ , and that some grid cells may enlarge their size, depending on the removed vertex; see Figure 8 right for an illustration. For each via-cell $C^{v}$ of $D\!\setminus\!\{v\}$ in the empty side of $\Delta_{1}$ , we denote by $G^{v}$ the grid cell of $D\!\setminus\!\{v\}$ containing $C^{v}$ . Observe that $G^{v}$ is either an (enlarged) grid cell of $D$ or two such grid cells glued along an edge $r_{v}$ . With the following lemma, we obtain that the grid cells containing via-cells of the subdrawings have common intersections in the grid cells of $D$ .

Lemma 14.

Let $w_{1},w_{2},\ldots,w_{s}$ be the set of vertices in $V\!\setminus\!V_{0}$ such that for every $w_{i}$ , the grid cell $G^{w_{i}}$ in $D\!\setminus\!\{w_{i}\}$ is placed before $m$ . Let $x_{1},x_{2},\ldots,x_{t}$ be the set of vertices in $V\!\setminus\!V_{0}$ such that for every $x_{i}$ , the grid cell $G^{x_{i}}$ in $D\!\setminus\!\{x_{i}\}$ is placed after $m$ . Then

1.

If $s\geq 2$ , the common intersection of $G^{w_{1}},G^{w_{2}},\ldots,G^{w_{s}}$ is a grid cell of $D$ placed before $m$ .
2.

If $t\geq 2$ , the common intersection of $G^{x_{1}},G^{x_{2}},\ldots,G^{x_{t}}$ is a grid cell of $D$ placed after $m$ .
3.

It $s\geq 2$ and $t\geq 2$ , then the two obtained grid cells of $D$ are $G_{c}$ and $G_{c+1}$ , respectively.

Proof Sketch.

(1) Given $w_{i}$ and $w_{j}$ , we show that $G^{w_{i}}\cap G^{w_{j}}$ is a grid cell of $D$ by analyzing the intersections among $G^{w_{i}},G^{w_{j}}$ and $G^{w_{i}w_{j}}$ , for the different possibilities of the positions of $r_{w_{i}}$ and $r_{w_{j}}$ . Then we show by contradiction that $G^{w_{1}},$ $G^{w_{2}},\ldots,G^{w_{s}}$ have a common intersection, which is a grid cell of $D$ placed before $m$ . Assuming that $G^{w_{i}}\cap G^{w_{j}}\neq G^{w_{j}}\cap G^{w_{k}}$ , we show that $G^{w_{i}}$ and $G^{w_{k}}$ cannot be contained in $G^{w_{i}w_{k}}$ , a contradiction. (2) is proved in a similar way. To prove (3), we show by contradiction that $G_{c}$ (respectively $G_{c+1}$ ) is contained in $G^{w_{i}}$ (respectively $G^{x_{i}}$ ) for any $i$ , so $G_{c}$ and $G_{c+1}$ must be the common grid cells. $\hfill\blacktriangleleft$

Next we show that with enough vertices in total, we also obtain vi-cells of $D$ in the (shared) grid cells we found in $D$ .

Lemma 15.

Suppose that for the via-cells $C^{w_{1}},C^{w_{2}},\ldots,C^{w_{s}}$ with $s\geq 2$ , the corresponding grid cells $G^{w_{1}},G^{w_{2}},\ldots,G^{w_{s}}$ in $D\!\setminus\!\{w_{1}\},D\!\setminus\!\{w_{2}\},\ldots,D\!\setminus\!\{w_{s}\}$ , respectively, contain a common grid cell $G$ of $D$ . Then $C^{w_{1}},C^{w_{2}},\ldots,C^{w_{s}}$ also contain a common vi-cell $C$ of $D$ .

Proof Sketch.

We first prove that if $G^{w_{i}}$ and $G^{w_{j}}$ contain a common grid cell $G$ , then the interior of $C^{w_{i}}$ (or $C^{w_{j}}$ ) and the interior of $G$ are not disjoint. Using this result, if $G$ has only one vertex on its boundary, then the lemma trivially holds. If $G$ contains two vertices on its boundary, we partition $C^{w_{1}},C^{w_{2}},\ldots,C^{w_{s}}$ into three sets $S_{1},S_{2}$ , and $S_{3}$ , where $S_{1}$ contains the cells $C^{w_{i}}$ that are incident to only one of the vertices, $S_{2}$ contains the cells $C^{w_{i}}$ that are incident to only the other vertex, and $S_{3}$ contains the cells $C^{w_{i}}$ that are incident to both vertices. We then prove that one of $S_{1}$ and $S_{2}$ must be empty, so $C^{w_{1}},C^{w_{2}},\ldots,C^{w_{s}}$ must all be incident to the same vertex of $G$ and share a common vi-cell $C$ of $D$ . $\hfill\blacktriangleleft$

The following lemma shows that $D$ contains a pair of antipodal vi-cells.

Lemma 16.

For $n\geq 12$ , there exists a pair $(C,C^{\prime})$ of antipodal vi-cells in $D$ .

Proof Sketch.

For $i=1,\ldots,7$ , let $w_{i}$ be a vertex not in $V_{0}$ and let $(C^{w_{i}}_{1},C^{w_{i}}_{2})$ be a pair of antipodal vi-cells in the subdrawing $D\!\setminus\!\{w_{i}\}$ . For any pair of antipodal vi-cells of $V_{0}$ , one of the cells is in $\Delta_{1}$ and the other in $\Delta_{2}$ . Hence, by Lemma 13, $C_{1}^{w_{i}}$ must lie in $\Delta_{1}$ and $C_{2}^{w_{i}}$ in $\Delta_{2}$ for any $i$ . Using Lemmas 14 and 15, we show that at least four of the vi-cells $C_{1}^{w_{i}}$ share a common vi-cell $C$ in $\Delta_{1}$ and a common vi-cell $C^{\prime}$ in $\Delta_{2}$ for the corresponding vi-cells $C_{2}^{w_{i}}$ . By the antipodality of the pairs $(C^{w_{i}}_{1},C^{w_{i}}_{2})$ that contain $(C,C^{\prime})$ , we prove the antipodality of $(C,C^{\prime})$ by showing for all triangles of $D$ that $C$ and $C^{\prime}$ are on different sides. $\hfill\blacktriangleleft$

4 Characterization via bipartition

This section is devoted to the proof of Theorem 2. Before starting with the proof, we introduce the concept of compatibility of vertices. Given a realizable rotation system of $K_{n}$ , let $R_{v_{1}}=\{v_{2}=w_{1},w_{2},\ldots,w_{n-1}\}$ and $R_{v_{2}}=\{v_{1}=t_{1},t_{2},\ldots,t_{n-1}\}$ be the (clockwise) rotations of $v_{1}$ and $v_{2}$ , respectively. We say that $v_{1}$ and $v_{2}$ are compatible (or that $v_{1}$ is compatible with $v_{2}$ ) if $\{v_{1},t_{2},\ldots,t_{n-1}\}=\{v_{1},w_{i},w_{i-1},\ldots,w_{2},w_{n-1},w_{n% -2},\ldots,w_{i+1}\}$ , for some $i\in\{1,2,\ldots,n\}$ . Note that if $v_{1}$ and $v_{2}$ are compatible and $i$ is 1 or $n$ , then $\{v_{1},t_{2},\ldots,t_{n-1}\}=\{v_{1},w_{n-1},w_{n-2},\ldots,w_{2}\}$ .

Next we consider pairs of antipodal vi-cells in simple drawings (and thus in generalized twisted drawings) and show that each such pair contains a pair of compatible vertices. For any antipodal vi-cell pair $(C_{1},C_{2})$ in a simple drawing of $K_{n}$ , there exist two vertices $v_{1}\neq v_{2}$ such that $v_{1}$ and $v_{2}$ are incident to $C_{1}$ and $C_{2}$ , respectively [4]. The following lemma implies that $v_{1}$ and $v_{2}$ are compatible.

Figure 9: The rotations of

v_{1}

and

v_{2}

.

Figure 10:

w_{k}

cannot appear after

C_{2}

around

v_{2}

.

Lemma 17.

Let $D$ be a realization of a generalized twisted rotation system of $K_{n}$ with $n\geq 3$ . Let $(C_{1},C_{2})$ be a pair of antipodal vi-cells of $D$ , and let $v_{1}$ and $v_{2}$ be vertices of $D$ incident to $C_{1}$ and $C_{2}$ , respectively, with $v_{2}\neq v_{1}$ . Assume that $R_{v_{1}}=\{v_{2}=w_{1},w_{2},\ldots,w_{n-1}\}$ is the (clockwise) rotation of $v_{1}$ , and that the edges $v_{1}w_{i}$ and $v_{1}w_{i+1}$ define part of the boundary of $C_{1}$ , for some $i\in\{1,\ldots,n-1\}$ . Then the following statements hold.

(i)

If $i\in\{2,3,\ldots,n-2\}$ then the (clockwise) rotation of $v_{2}$ is $\{v_{1},w_{i},w_{i-1},\ldots,w_{2},w_{n-1},$ $w_{n-2},$ $\ldots,w_{i+1}\}$ and the edges $v_{2}w_{2}$ and $v_{2}w_{n-1}$ define part of the boundary of $C_{2}$ .
(ii)

If $i=1$ then the (clockwise) rotation of $v_{2}$ is $\{v_{1},w_{n-1},w_{n-2},\ldots,w_{2}\}$ and the edges $v_{2}v_{1}$ and $v_{2}w_{n-1}$ define part of the boundary of $C_{2}$ .
(iii)

If $i=n-1$ then the (clockwise) rotation of $v_{2}$ is $\{v_{1},w_{n-1},w_{n-2},\ldots,w_{2}\}$ and the edges $v_{2}v_{1}$ and $v_{1}w_{2}$ define part of the boundary of $C_{2}$ .

Proof Sketch.

We sketch the proof of (i); the proofs of (ii) and (iii) are very similar. Figure 9 shows an example of the rotations of $v_{1}$ and $v_{2}$ . Assume that the clockwise rotation of $v_{2}$ is $\{v_{1}=t_{1},t_{2},\ldots,t_{n-1}\}$ and that the edges $v_{2}t_{j}$ and $v_{2}t_{j+1}$ , for some $j\in\{1,\ldots,n-1\}$ , define part of the boundary of $C_{2}$ . To place $w_{k}$ in the rotation of $v_{1}$ and $v_{2}$ with respect to $C_{1}$ and $C_{2}$ , we consider for $w_{k}$ with $2\leq k\leq i$ the triangle spanned by $v_{1}$ , $v_{2}$ and $w_{k}$ . As $C_{1}$ and $C_{2}$ are antipodal, they must lie on different sides of the triangle. This is not possible if $w_{k}$ corresponds to a vertex $t_{k^{\prime}}$ with $j+1\leq k^{\prime}\leq n-1$ (see Figure 10 for a depiction). Thus, if a vertex appears before (via analogous arguments after) $C_{1}$ around $v_{1}$ clockwise from $v_{2}$ , then it also appears before (after) $C_{2}$ around $v_{2}$ clockwise from $v_{1}$ .

Figure 11:

w_{k}

cannot appear before

w_{l}

around

v_{2}

.

For two vertices $w_{k}$ and $w_{l}$ with $2\leq k<l\leq i$ , we show that $w_{l}$ appears before $w_{k}$ in the clockwise rotation of $v_{2}$ from $v_{1}$ by contradiction. Consider the edges $v_{1}w_{l}$ and $v_{2}w_{l}$ . If $w_{k}$ appears before $w_{l}$ in the clockwise rotation of $v_{2}$ from $v_{1}$ , then the edges $v_{1}w_{l}$ and $v_{2}w_{l}$ emanate in different sides of the triangle $v_{1}v_{2}w_{k}$ from $v_{1}$ and $v_{2}$ . From simplicity of the drawing and the fact that each realization of a generalized twisted rotation system of $K_{4}$ contains exactly one crossing [5], we can determine how that edge $w_{l}w_{k}$ must behave (see Figure 11 for a depiction). We then show that with this drawing, $C_{1}$ and $C_{2}$ must lie on the same side of the triangle $v_{1}w_{k}w_{l}$ , which contradicts that they are antipodal cells. $\hfill\blacktriangleleft$

Figure 12: Illustrating the proof of Theorem 2 (i) and (iii).

Figure 13:

C_{1}

and

C_{2}

are on different sides of

\Delta xyz

. Left:

x

,

y

, and

z

belong to the same set of the bipartition. Right:

x

and

y

belong to one of the sets and

z

to the other.

Using Lemma 17 we can prove Theorem 2.

Proof Sketch of Theorem 2.

If $R$ is generalized twisted, then there exists a pair $(C_{1},C_{2})$ of antipodal vi-cells in $D$ , and we show that a bipartition of the vertices satisfies (i)–(v). Let $v_{1}$ be a vertex of $V$ incident to $C_{1}$ and let $v_{2}\neq v_{1}$ be a vertex of $V$ incident to $C_{2}$ . Suppose that $\{v_{2}=w_{1},w_{2},\ldots,w_{n-1}\}$ is the (clockwise) rotation of $v_{1}$ such that $v_{1}w_{i}$ and $v_{1}w_{i+1}$ define part of the boundary of $C_{1}$ , for some $i\in\{1,\ldots,n-1\}$ . Let $A$ and $B$ be defined as follows: if $i\not\in\{1,n-1\}$ , set $A:={w_{i+1},...,w_{n-1}}$ , $B:={w_{2},...,w_{i}}$ ; if $i=1$ , set $A:=\{v_{1},w_{n-1},w_{n-2},\ldots,w_{2}\}$ , $B:=\emptyset$ ; if $i=n-1$ , set $A:=\emptyset$ , $B:=\{v_{1},w_{n-1},w_{n-2},\ldots,w_{2}\}$ . We show that this bipartition satisfies (i)–(v).

Figure 14:

C_{1}

and

C_{2}

are on different sides of

\Delta v_{1}xy

. Left:

x

and

y

belong to the same set of the bipartition. Right:

x

and

y

belong to different sets of the bipartition.

Figure 15:

C_{1}

and

C_{2}

are on different sides of

\Delta v_{1}v_{2}x

.

To prove that (i) holds, we take two vertices $a$ and $a^{\prime}$ in $A$ . (If $A$ contains at most one vertex, (i) is vacuously true.) We use Lemma 17 to obtain the rotation of $v_{1}$ and $v_{2}$ and information on the bounding edges of $C_{1}$ and $C_{2}$ . We conclude that the edge $aa^{\prime}$ crosses $v_{1}v_{2}$ because otherwise $C_{1}$ and $C_{2}$ would be on the same side of the triangle $v_{1}aa^{\prime}$ (see Figure 12(left) for an example) contradicting that $C_{1}$ and $C_{2}$ are antipodal. Thus, (i) follows and, by analogous arguments for $B$ , (ii) follows.

To prove that (iii) holds for $A$ and $B$ , we take vertices $a\in A$ and $b\in B$ . By Lemma 17, $b$ is before $C_{1}$ and $a$ is after $C_{1}$ around $v_{1}$ . Thus, the edge $a b$ cannot cross $v_{1}v_{2}$ so that $C_{1}$ and $C_{2}$ are on different sides of $\Delta v_{1}ab$ (see Figure 12(right) for an example). Hence, (iii) follows. Finally, (iv)–(v) follow directly from the definitions of $A$ and $B$ .

To prove the other direction, we assume that $R$ and $D$ are a rotation system and drawing fulfilling (i)–(v), and show that $R$ is generalized twisted. Let $\{v_{2},b_{1},\ldots,b_{n_{1}},$ $a_{1},\ldots,a_{n_{2}}\}$ be the (clockwise) rotation of $v_{1}$ beginning at $v_{2}$ , and $\{v_{1},b^{\prime}_{1},\ldots,b^{\prime}_{n_{1}},$ $a^{\prime}_{1},\ldots,a^{\prime}_{n_{2}}\}$ be the (clockwise) rotation of $v_{2}$ beginning at $v_{1}$ . Let $C_{1}$ be the vi-cell of $D$ defined by the edges $v_{1}b_{n_{1}}$ and $v_{1}a_{1}$ , and $C_{2}$ be the vi-cell of $D$ defined by the edges $v_{2}b^{\prime}_{n_{1}}$ and $v_{2}a^{\prime}_{1}$ . We show that $C_{1}$ and $C_{2}$ are antipodal and thus $R$ is generalized twisted by showing for all possible triangles in $D$ that $C_{1}$ and $C_{2}$ are on different sides of that triangle. We analyze the triangles and show the following. If $v_{1}$ and $v_{2}$ are not incident to $\Delta$ , the number of crossings give that $v_{1}$ and $v_{2}$ – and thus $C_{1}$ and $C_{2}$ – are on different sides of $\Delta$ (see Figure 13). If $v_{1}$ or $v_{2}$ are incident to $\Delta$ , we use $C_{1}$ and $C_{2}$ being on different ends of $v_{1}v_{2}$ to show that $C_{1}$ and $C_{2}$ are on different sides of $\Delta$ (see Figures 14 and 15). $\hfill\blacktriangleleft$

5 Efficient algorithms

In this section, we turn to the algorithmic aspect and prove Theorem 3.

To check whether an abstract rotation system of $K_{n}$ is generalized twisted, by Theorem 1, only the subrotation systems induced by five vertices need checking. This can be done in $O(n^{5})$ time. (The only exception where subdrawings are not sufficient are abstract rotation systems of $K_{6}$ , but for $n=6$ all three generalized twisted rotation systems are known.) Alternatively, one can first check in $O(n^{5})$ time whether the rotation system is realizable [2, 20]. If it is not, it cannot be generalized twisted. If it is, we can use the following faster algorithm for realizable rotation systems of $K_{n}$ , which we developed using Theorem 2. The algorithm runs in $O(n^{2})$ time and in two steps, which we describe in the remainder of this section.

Step 1.

In the first step, the empty star triangles at an arbitrary vertex $x$ are computed.

Lemma 18.

Given a realizable rotation system $R$ of $K_{n}$ and a vertex $x$ of $R$ , the set of all empty star triangles at $x$ is the same in each realization of $R$ and can be computed from $R$ in $O(n^{2})$ time.

Proof Sketch.

By Lemma 5, a star triangle $x y z$ at $x$ is empty if and only if $y$ and $z$ are consecutive in the rotation of $x$ . Hence, there are at most $n-1$ empty star triangles at $x$ . Whether a triangle $x y z$ is a star triangle at $x$ is determined by whether there exists a vertex $w$ such that $x w$ crosses $y z$ . Since deciding for two edges if they cross each other can be done in constant time via the rotation system, deciding if a star triangle is empty requires $O(n)$ time. Thus, computing all empty star triangles at $x$ can be done in $O(n^{2})$ time. $\hfill\blacktriangleleft$

Step 2.

In the second step, the previously computed empty star triangles at $x$ and Theorem 2 are used to decide whether $R$ is generalized twisted.

Lemma 19.

Given a realizable rotation system $R$ of $K_{n}$ and the set of empty star triangles of a vertex $x$ of $R$ , it can be determined in $O(n^{2})$ time whether $R$ is generalized twisted.

Proof Sketch.

By Lemma 17, every drawing with generalized twisted rotation system has a pair $(v_{1},v_{2})$ of compatible vertices. If $(C_{1},C_{2})$ is a pair of antipodal vi-cells, then $v_{1}$ and $v_{2}$ lie on the boundary of $C_{1}$ and $C_{2}$ (or vice versa). We look for compatible vertices using empty triangles. Let $x$ be the vertex with given empty star triangles. If there are not exactly two empty star triangles at $x$ , then $R$ is not generalized twisted by Lemma 6. Otherwise, we denote by $\Delta=xyz$ and $\Delta^{\prime}=xy^{\prime}z^{\prime}$ the two empty star triangles at $x$ . (Possibly, $y$ or $z$ coincides with $y^{\prime}$ or $z^{\prime}$ .) Using Lemma 6, we can show that if there is a compatible pair of vertices it must be in $S=\{(y,y^{\prime}),(y,z^{\prime}),(y,x),(z,y^{\prime}),(z,z^{\prime}),$ $(z,x),(x,y^{\prime}),(x,z^{\prime})\}$ . Checking compatibility of any pair in $S$ by comparing their rotation systems takes linear time.

For every such potentially compatible pair $(v_{1},v_{2})$ , we check properties (i)–(v) of Theorem 2. Let $\{v=w_{1},w_{2},\ldots,w_{n-1}\}$ be the rotation of $v_{1}$ . We define $A$ and $B$ as follows. If the rotation of $v_{2}$ is $\{v_{1},w_{n-1},\ldots,w_{2}\}$ , then $B=\{w_{2},\ldots,w_{n-1}\}$ and $A=\emptyset$ (or vice versa), and if the rotation of $v_{2}$ is $\{v_{1},w_{i},\ldots,w_{2},w_{n-1},\ldots,w_{i+1}\}$ , for some $i$ different from $1$ and $n-1$ , then $B=\{w_{2},\ldots,w_{i}\}$ and $A=\{w_{i+1},\ldots,w_{n-1}\}$ . Then $A$ and $B$ clearly satisfy (iv) and (v) of Theorem 2. Checking if (i), (ii), and (iii) of Theorem 2 are satisfied requires $O(n^{2})$ time.

Therefore, since $|S|$ is a constant, deciding if there is a pair $(v_{1},v_{2})$ in $S$ such that $v_{1}$ and $v_{2}$ are compatible and the properties (i)–(v) of Theorem 2 are satisfied for this pair can be done in $O(n^{2})$ time. $\hfill\blacktriangleleft$

6 Conclusion and open problems

We presented two new characterizations for generalized twisted drawings based solely on their rotation systems. From these, we derived an $O(n^{5})$ -time algorithm that decides whether an abstract rotation system of $K_{n}$ is generalized twisted and an $O(n^{2})$ -time algorithm to decide whether a realizable rotation system is generalized twisted. The obvious open question is whether the decision can also be done faster for abstract rotation systems. The quadratic time algorithm we give does not directly apply to them. There is a non-realizable rotation system of $K_{5}$ for which the output of the algorithm depends on the choice of vertex $x$ and might be ’generalized twisted’ or ’not generalized twisted’.

Generalized twisted drawings have been useful before, for example to find large plane substructures in simple drawings [5, 15]. Overcoming their rather geometrical definition, our new combinatorial characterizations might ease work with generalized twisted drawings and foster further results with this flavor. For example, Pach, Solymosi, and Tóth [21] showed that every simple drawing of a complete graph on $n$ vertices contains $O(\log^{\frac{1}{8}}n)$ vertices inducing a complete subdrawing that is either convex or twisted. Recently, Suk and Zeng [25, 26] improved this result to $(\log n)^{\frac{1}{4}-o(1)}$ vertices. As both convex and twisted drawings contain large plane paths and cycles, this provides lower bounds on the size of plane paths and cycles that every simple drawing contains. It would be interesting to generalize this to show that every simple drawing contains a large generalized twisted or generalized convex subdrawing. Generalized convex drawings are – like generalized twisted drawings – a family of drawings of graphs that are well investigated [9, 11, 12]. Similarly to generalized twisted drawings, they admit characterizations via small constant sized subrotation systems [9]. Thus, a result guaranteeing the existence of a large generalized convex or generalized twisted drawing would help to extend our knowledge on simple drawings and, for example, to improve the lower bounds on the size of plane paths and cycles. We expect that this and several other questions on simple drawings can be tackled using the characterizations of this paper – independently or in combination. Especially, since the two given characterizations are very different from each other, with Theorem 1 being on all small subrotation systems and Theorem 2 being on two specific points and their rotation in the whole rotation system, they might foster the application of different other tools to obtain new results.

References

[1] URL: https://figshare.com/projects/g-twisted_rotation_systems/184474.
[2] Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Thomas Hackl, Jürgen Pammer, Alexander Pilz, Pedro Ramos, Gelasio Salazar, and Birgit Vogtenhuber. All good drawings of small complete graphs. In Proc. $31^{st}$ European Workshop on Computational Geometry EuroCG ’15, pages 57–60, 2015. URL: http://www.ist.tu-graz.ac.at/files/publications/geometry/aafhpprsv-agdsc-15.pdf.
[3] Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, and Gelasio Salazar. Shellable drawings and the cylindrical crossing number of $K_{n}$ . Discret. Comput. Geom., 52(4):743–753, 2014. doi:10.1007/S00454-014-9635-0.
[4] Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted ways to find plane structures in simple drawings of complete graphs. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, volume 224 of LIPIcs, pages 5:1–5:18, 2022. doi:10.4230/LIPICS.SOCG.2022.5.
[5] Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted ways to find plane structures in simple drawings of complete graphs. Discret. Comput. Geom., 71(1):40–66, 2024. doi:10.1007/S00454-023-00610-0.
[6] Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Pedro Ramos, Vera Sacristán, and Birgit Vogtenhuber. Empty triangles in good drawings of the complete graph. Graphs Comb., 31(2):335–345, 2015. doi:10.1007/S00373-015-1550-5.
[7] Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Drawings of k ${}_{\mbox{n}}$ with the same rotation scheme are the same up to reidemeister moves (gioan’s theorem). Australas. J Comb., 67:131–144, 2017. URL: http://ajc.maths.uq.edu.au/pdf/67/ajc_v67_p131.pdf.
[8] Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Levi’s lemma, pseudolinear drawings of $K_{n}$ , and empty triangles. J. Graph Theory, 87(4):443–459, 2018. doi:10.1002/JGT.22167.
[9] Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Convex drawings of the complete graph: topology meets geometry. Ars Math. Contemp., 22(3):3, 2022. doi:10.26493/1855-3974.2134.AC9.
[10] Martin Balko, Radoslav Fulek, and Jan Kynčl. Crossing numbers and combinatorial characterization of monotone drawings of $K_{n}$ . Discret. Comput. Geom., 53(1):107–143, 2015. doi:10.1007/S00454-014-9644-Z.
[11] Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, and Manfred Scheucher. Plane Hamiltonian cycles in convex drawings. In 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 18:1–18:16, 2024. doi:10.4230/LIPICS.SOCG.2024.18.
[12] Helena Bergold, Joachim Orthaber, Manfred Scheucher, and Felix Schröder. Holes in convex and simple drawings. In Stefan Felsner and Karsten Klein, editors, 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, volume 320 of LIPIcs, pages 5:1–5:9, 2024. doi:10.4230/LIPICS.GD.2024.5.
[13] Stefan Felsner, Sandro Roch, and Manfred Scheucher. Arrangements of pseudocircles: On digons and triangles. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, volume 13764 of Lecture Notes in Computer Science, pages 441–455, 2022. doi:10.1007/978-3-031-22203-0_32.
[14] Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Empty triangles in generalized twisted drawings of $K_{n}$ . In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, volume 13764, pages 40–48, 2022. doi:10.1007/978-3-031-22203-0_4.
[15] Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Empty triangles in generalized twisted drawings of $K_{n}$ . J. Graph Algorithms Appl., 27(8):721–735, 2023. doi:10.7155/JGAA.00637.
[16] Emeric Gioan. Complete graph drawings up to triangle mutations. In Dieter Kratsch, editor, 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005, volume 3787 of Lecture Notes in Computer Science, pages 139–150, 2005. doi:10.1007/11604686_13.
[17] Emeric Gioan. Complete graph drawings up to triangle mutations. Discret. Comput. Geom., 67(4):985–1022, 2022. doi:10.1007/S00454-021-00339-8.
[18] Heiko Harborth and Ingrid Mengersen. Drawings of the complete graph with maximum number of crossings. Congressus Numerantium, pages 225–225, 1992.
[19] Jan Kynčl. Improved enumeration of simple topological graphs. Discret. Comput. Geom., 50(3):727–770, 2013. doi:10.1007/S00454-013-9535-8.
[20] Jan Kynčl. Simple realizability of complete abstract topological graphs simplified. Discret. Comput. Geom., 64(1):1–27, 2020. doi:10.1007/S00454-020-00204-0.
[21] János Pach, József Solymosi, and Géza Tóth. Unavoidable configurations in complete topological graphs. Discrete Comput Geometry, 30:311–320, 2003. doi:10.1007/s00454-003-0012-9.
[22] Yan Alves Radtke, Stefan Felsner, Johannes Obenaus, Sandro Roch, Manfred Scheucher, and Birgit Vogtenhuber. Flip graph connectivity for arrangements of pseudolines and pseudocircles. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pages 4849–4871, 2024. doi:10.1137/1.9781611977912.172.
[23] Marcus Schaefer. Taking a detour; or, Gioan’s theorem, and pseudolinear drawings of complete graphs. Discret. Comput. Geom., 66(1):12–31, 2021. doi:10.1007/S00454-021-00296-2.
[24] Marcus Schaefer, Jean Cardinal, and Tillmann Miltzow. The existential theory of the reals as a complexity class: A compendium, 2024. doi:10.48550/arXiv.2407.18006.
[25] Andrew Suk and Ji Zeng. Unavoidable patterns in complete simple topological graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, volume 13764 of Lecture Notes in Computer Science, pages 3–15, 2022. doi:10.1007/978-3-031-22203-0_1.
[26] Andrew Suk and Ji Zeng. Unavoidable patterns in complete simple topological graphs. Discret. Comput. Geom., 73(1):79–91, 2025. doi:10.1007/S00454-024-00658-6.

[bib.bib1] [1] URL: https://figshare.com/projects/g-twisted_rotation_systems/184474.

[bib.bib2] [2] Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Thomas Hackl, Jürgen Pammer, Alexander Pilz, Pedro Ramos, Gelasio Salazar, and Birgit Vogtenhuber. All good drawings of small complete graphs. In Proc. $31^{st}$ European Workshop on Computational Geometry EuroCG ’15, pages 57–60, 2015. URL: http://www.ist.tu-graz.ac.at/files/publications/geometry/aafhpprsv-agdsc-15.pdf.

[bib.bib3] [3] Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, and Gelasio Salazar. Shellable drawings and the cylindrical crossing number of $K_{n}$ . Discret. Comput. Geom., 52(4):743–753, 2014. doi:10.1007/S00454-014-9635-0.

[bib.bib4] [4] Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted ways to find plane structures in simple drawings of complete graphs. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, volume 224 of LIPIcs, pages 5:1–5:18, 2022. doi:10.4230/LIPICS.SOCG.2022.5.

[bib.bib5] [5] Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted ways to find plane structures in simple drawings of complete graphs. Discret. Comput. Geom., 71(1):40–66, 2024. doi:10.1007/S00454-023-00610-0.

[bib.bib6] [6] Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Pedro Ramos, Vera Sacristán, and Birgit Vogtenhuber. Empty triangles in good drawings of the complete graph. Graphs Comb., 31(2):335–345, 2015. doi:10.1007/S00373-015-1550-5.

[bib.bib7] [7] Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Drawings of k ${}_{\mbox{n}}$ with the same rotation scheme are the same up to reidemeister moves (gioan’s theorem). Australas. J Comb., 67:131–144, 2017. URL: http://ajc.maths.uq.edu.au/pdf/67/ajc_v67_p131.pdf.

[bib.bib8] [8] Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Levi’s lemma, pseudolinear drawings of $K_{n}$ , and empty triangles. J. Graph Theory, 87(4):443–459, 2018. doi:10.1002/JGT.22167.

[bib.bib9] [9] Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Convex drawings of the complete graph: topology meets geometry. Ars Math. Contemp., 22(3):3, 2022. doi:10.26493/1855-3974.2134.AC9.

[bib.bib10] [10] Martin Balko, Radoslav Fulek, and Jan Kynčl. Crossing numbers and combinatorial characterization of monotone drawings of $K_{n}$ . Discret. Comput. Geom., 53(1):107–143, 2015. doi:10.1007/S00454-014-9644-Z.

[bib.bib11] [11] Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, and Manfred Scheucher. Plane Hamiltonian cycles in convex drawings. In 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 18:1–18:16, 2024. doi:10.4230/LIPICS.SOCG.2024.18.

[bib.bib12] [12] Helena Bergold, Joachim Orthaber, Manfred Scheucher, and Felix Schröder. Holes in convex and simple drawings. In Stefan Felsner and Karsten Klein, editors, 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, volume 320 of LIPIcs, pages 5:1–5:9, 2024. doi:10.4230/LIPICS.GD.2024.5.

[bib.bib13] [13] Stefan Felsner, Sandro Roch, and Manfred Scheucher. Arrangements of pseudocircles: On digons and triangles. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, volume 13764 of Lecture Notes in Computer Science, pages 441–455, 2022. doi:10.1007/978-3-031-22203-0_32.

[bib.bib14] [14] Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Empty triangles in generalized twisted drawings of $K_{n}$ . In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, volume 13764, pages 40–48, 2022. doi:10.1007/978-3-031-22203-0_4.

[bib.bib15] [15] Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Empty triangles in generalized twisted drawings of $K_{n}$ . J. Graph Algorithms Appl., 27(8):721–735, 2023. doi:10.7155/JGAA.00637.

[bib.bib16] [16] Emeric Gioan. Complete graph drawings up to triangle mutations. In Dieter Kratsch, editor, 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005, volume 3787 of Lecture Notes in Computer Science, pages 139–150, 2005. doi:10.1007/11604686_13.

[bib.bib17] [17] Emeric Gioan. Complete graph drawings up to triangle mutations. Discret. Comput. Geom., 67(4):985–1022, 2022. doi:10.1007/S00454-021-00339-8.

[bib.bib18] [18] Heiko Harborth and Ingrid Mengersen. Drawings of the complete graph with maximum number of crossings. Congressus Numerantium, pages 225–225, 1992.

[bib.bib19] [19] Jan Kynčl. Improved enumeration of simple topological graphs. Discret. Comput. Geom., 50(3):727–770, 2013. doi:10.1007/S00454-013-9535-8.

[bib.bib20] [20] Jan Kynčl. Simple realizability of complete abstract topological graphs simplified. Discret. Comput. Geom., 64(1):1–27, 2020. doi:10.1007/S00454-020-00204-0.

[bib.bib21] [21] János Pach, József Solymosi, and Géza Tóth. Unavoidable configurations in complete topological graphs. Discrete Comput Geometry, 30:311–320, 2003. doi:10.1007/s00454-003-0012-9.

[bib.bib22] [22] Yan Alves Radtke, Stefan Felsner, Johannes Obenaus, Sandro Roch, Manfred Scheucher, and Birgit Vogtenhuber. Flip graph connectivity for arrangements of pseudolines and pseudocircles. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pages 4849–4871, 2024. doi:10.1137/1.9781611977912.172.

[bib.bib23] [23] Marcus Schaefer. Taking a detour; or, Gioan’s theorem, and pseudolinear drawings of complete graphs. Discret. Comput. Geom., 66(1):12–31, 2021. doi:10.1007/S00454-021-00296-2.

[bib.bib24] [24] Marcus Schaefer, Jean Cardinal, and Tillmann Miltzow. The existential theory of the reals as a complexity class: A compendium, 2024. doi:10.48550/arXiv.2407.18006.

[bib.bib25] [25] Andrew Suk and Ji Zeng. Unavoidable patterns in complete simple topological graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, volume 13764 of Lecture Notes in Computer Science, pages 3–15, 2022. doi:10.1007/978-3-031-22203-0_1.

[bib.bib26] [26] Andrew Suk and Ji Zeng. Unavoidable patterns in complete simple topological graphs. Discret. Comput. Geom., 73(1):79–91, 2025. doi:10.1007/S00454-024-00658-6.

Characterizing and Recognizing Twistedness

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Theorem 2.

Theorem 3.

Outline.

2 Preliminaries

Antipodal vi-cells.

Theorem 4 ([4]).

Empty star triangles.

Lemma 5 ([6]).

Lemma 6 ([15]).

Maximum crossing edges.

Lemma 7.

Lemma 8.

3 Characterization via subrotation systems induced by five vertices

Theorem 9.

Proof of Theorem 1.

3.1 Proof sketch of Theorem 9

Lemma 10.

Case 1: Two adjacent empty star triangles at a vertex 𝒖.

Lemma 11.

Case 2: No vertex with two adjacent empty star triangles.

Lemma 12.

Proof Sketch.

Lemma 13.

Lemma 14.

Proof Sketch.

Lemma 15.

Proof Sketch.

Lemma 16.

Proof Sketch.

4 Characterization via bipartition

Lemma 17.

Proof Sketch.

Proof Sketch of Theorem 2.

5 Efficient algorithms

Step 1.

Lemma 18.

Proof Sketch.

Step 2.

Lemma 19.

Proof Sketch.

6 Conclusion and open problems

References

Case 1: Two adjacent empty star triangles at a vertex $𝒖$ .