A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph $K_n$ admits a plane Hamiltonian cycle. It turned out that already the existence of much simpler non-crossing substructures in such drawings is hard to prove. Recent progress was made by Aichholzer et al. and by Suk and Zeng who proved the existence of a plane path of length $Ω(\log n / \log \log n)$ and of a plane matching of size $Ω(n^{1/2})$ in every simple drawing of $K_n$. Instead of studying simpler substructures, we prove Rafla's conjecture for the subclass of convex drawings, the most general class in the convexity hierarchy introduced by Arroyo et al. Moreover, we show that every convex drawing of $K_n$ contains a plane Hamiltonian path between each pair of vertices (Hamiltonian connectivity) and a plane $k$-cycle for each $3 \leq k \leq n$ (pancyclicity), and present further results on maximal plane subdrawings.

In this paper, we consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-2}$ which is saturated for convex $n$-gons. That is, the set contains no $n$ points in convex position while the addition of any new point creates such a configuration. This demonstrates that the saturation number is smaller than the Ramsey number for the Erdős--Szekeres problem. The proof also shows that the original Erdős--Szekeres construction is indeed saturated. Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number.

Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number $B_n$ of non-isomorphic simple arrangements of $n$ pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that $B_n$ is in the order of $2^{Θ(n^2)}$ and finding asymptotic bounds on $b_n = \frac{\log_2(B_n)}{n^2}$ remains a challenging task. In 2011, Felsner and Valtr showed that $0.1887 \leq b_n \le 0.6571$ for sufficiently large $n$. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to $0.2083$. Their approach utilizes the known values of $B_n$ for up to $n=12$. We tackle the lower bound by utilizing dynamic programming and the Lindström-Gessel-Viennot lemma. Our new bound is $b_n \geq 0.2721$ for sufficiently large $n$. The result is based on a delicate interplay of theoretical ideas and computer assistance.

Gons and holes in point sets have been extensively studied in the literature. For simple drawings of the complete graph a generalization of the Erdős--Szekeres theorem is known and empty triangles have been investigated. We introduce a notion of $k$-holes for simple drawings and survey generalizations thereof, like empty $k$-cycles. We present a family of simple drawings without $4$-holes and prove a generalization of Gerken's empty hexagon theorem for convex drawings. A crucial intermediate step is the structural investigation of pseudolinear subdrawings in convex drawings. With respect to empty $k$-cycles, we show the existence of empty $4$-cycles in every simple drawing of $K_n$ and give a construction that admits only $Θ(n^2)$ of them.

Flip graphs of combinatorial and geometric objects are at the heart of many deep structural insights and connections between different branches of discrete mathematics and computer science. They also provide a natural framework for the study of reconfiguration problems. We study flip graphs of arrangements of pseudolines and of arrangements of pseudocircles, which are combinatorial generalizations of lines and circles, respectively. In both cases we consider triangle flips as local transformation and prove conjectures regarding their connectivity.

Abstract Satisfiability solving has been used to tackle a range of long-standing open math problems in recent years. We add another success by solving a geometry problem that originated a century ago. In the 1930s, Esther Klein’s exploration of unavoidable shapes in planar point sets in general position showed that every set of five points includes four points in convex position. For a long time, it was open if an empty hexagon, i.e., six points in convex position without a point inside, can be avoided. In 2006, Gerken and Nicolás independently proved that the answer is no. We establish the exact bound: Every 30-point set in the plane in general position contains an empty hexagon. Our key contributions include an effective, compact encoding and a search-space partitioning strategy enabling linear-time speedups even when using thousands of cores.

In 1926, Levi showed that, for every pseudoline arrangement $\mathcal{A}$ and two points in the plane, $\mathcal{A}$ can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in $\mathbb{R}^d$ with a hyperplane containing $d$ prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in $\mathbb{R}^3$ which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks $r \geq 4$ there exist signotopes which are not extendable for two prescribed points. Our conjecture is supported by examples in ranks 4, 6, 8, 10, and 12 that were found with a SAT based approach.

We consider point sets in the real projective plane ℝ𝒫² and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős-Szekeres-type problems. We provide asymptotically tight bounds for a variant of the Erdős-Szekeres theorem about point sets in convex position in ℝ𝒫², which was initiated by Harborth and Möller in 1994. The notion of convex position in ℝ𝒫² agrees with the definition of convex sets introduced by Steinitz in 1913. For k ≥ 3, an (affine) k-hole in a finite set S ⊆ ℝ² is a set of k points from S in convex position with no point of S in the interior of their convex hull. After introducing a new notion of k-holes for points sets from ℝ𝒫², called projective k-holes, we find arbitrarily large finite sets of points from ℝ𝒫² with no projective 8-holes, providing an analogue of a classical result by Horton from 1983. We also prove that they contain only quadratically many projective k-holes for k ≤ 7. On the other hand, we show that the number of k-holes can be substantially larger in ℝ𝒫² than in ℝ² by constructing, for every k ∈ {3,… ,6}, sets of n points from ℝ² ⊂ ℝ𝒫² with Ω(n^{3-3/5k}) projective k-holes and only O(n²) affine k-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in ℝ𝒫² and about some algorithmic aspects. The study of extremal problems about point sets in ℝ𝒫² opens a new area of research, which we support by posing several open problems.

Rota's basis conjecture (RBC) states that given a collection $\mathcal{B}$ of $n$ bases in a matroid $M$ of rank $n$, one can always find $n$ disjoint rainbow bases with respect to $\mathcal{B}$. In this paper, we show that if $M$ has girth at least $n-o(\sqrt{n})$, and no element of $M$ belongs to more than $o(\sqrt{n})$ bases in $\mathcal{B}$, then one can find at least $n - o(n)$ disjoint rainbow bases with respect to $\mathcal{B}$. This result can be seen as an extension of the work of Geelen and Humphries, who proved RBC in the case where $M$ is paving, and $\mathcal{B}$ is a pairwise disjoint collection. We make extensive use of the cascade idea introduced by Bucić et al.

Abstract A pseudocircle is a simple closed curve on the sphere or in the plane. The study of arrangements of pseudocircles was initiated by Grünbaum, who defined them as collections of simple closed curves that pairwise intersect in exactly two crossings. Grünbaum conjectured that the number of triangular cells $$p_3$$ p 3 in digon-free arrangements of n pairwise intersecting pseudocircles is at least $$2n-4$$ 2 n - 4 . We present examples to disprove this conjecture. With a recursive construction based on an example with 12 pseudocircles and 16 triangles we obtain a family of intersecting digon-free arrangements with $$p_3({\mathscr {A}})/n \rightarrow 16/11 = 1.\overline{45}$$ p 3 ( A ) / n → 16 / 11 = 1 . 45 ¯ . We expect that the lower bound $$p_3({\mathscr {A}}) \ge 4n/3$$ p 3 ( A ) ≥ 4 n / 3 is tight for infinitely many simple arrangements. It may however be true that all digon-free arrangements of n pairwise intersecting circles have at least $$2n-4$$ 2 n - 4 triangles. For pairwise intersecting arrangements with digons we have a lower bound of $$p_3 \ge 2n/3$$ p 3 ≥ 2 n / 3 , and conjecture that $$p_3 \ge n-1$$ p 3 ≥ n - 1 . Concerning the maximum number of triangles in pairwise intersecting arrangements of pseudocircles, we show that $$p_3 \le \frac{4}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) +O(n)$$ p 3 ≤ 4 3 n 2 + O ( n ) . This is essentially best possible because there are families of pairwise intersecting arrangements of n pseudocircles with $$p_3 = \frac{4}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) $$ p 3 = 4 3 n 2 . The paper contains many drawings of arrangements of pseudocircles and a good fraction of these drawings was produced automatically from the combinatorial data produced by our generation algorithm. In the final section we describe some aspects of the drawing algorithm.

We investigate which planar point sets allow simultaneous straight-line embeddings of all planar graphs on a fixed number of vertices. We first show that at least $(1.293-o(1))n$ points are required to find a straight-line drawing of each $n$-vertex planar graph (vertices are drawn as the given points); this improves the previous best constant $1.235$ by Kurowski (2004). Our second main result is based on exhaustive computer search: We show that no set of 11 points exists, on which all planar 11-vertex graphs can be simultaneously drawn plane straight-line. This strengthens the result by Cardinal, Hoffmann, and Kusters (2015), that all planar graphs on $n \le 10$ vertices can be simultaneously drawn on particular $n$-universal sets of $n$ points while there are no $n$-universal sets of size $n$ for $n \ge 15$. We also provide 49 planar 11-vertex graphs which cannot be simultaneously drawn on any set of 11 points. This, in fact, is another step towards a (negative) answer of the question, whether every two planar graphs can be drawn simultaneously - a question raised by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw, and Mitchell (2007).

A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.