Source author record

Manfred Scheucher

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics math.PR math.MG

Catalog footprint

Research overview

12works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Coloring circle arrangements: New $4$ -chromatic planar graphs

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most $3$ . Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of arrangements of (pseudo-)circles. In this paper the conjecture is verified for $\triangle$ -saturated pseudocircle arrangements, i.e., for arrangements where one color class of the 2-coloring of faces consists of triangles only, as well as for further classes of (pseudo-)circle arrangements. These results are complemented by a construction which maps $\triangle$ -saturated arrangements with a pentagonal face to arrangements with 4-chromatic 4-regular arrangement graphs. This "corona" construction has similarities with the crowning construction introduced by Koester (1985). Based on exhaustive experiments with small arrangements we propose three strengthenings of the original conjecture. We also investigate fractional colorings. It is shown that the arrangement graph of every arrangement $\mathcal{A}$ of pairwise intersecting pseudocircles is "close" to being $3$ -colorable. More precisely, the fractional chromatic number $χ_f(\mathcal{A})$ of the arrangement graph is bounded from above by $χ_f(\mathcal{A}) \le 3+O(\frac{1}{n})$ , where $n$ is the number of pseudocircles of $\mathcal{A}$ . Furthermore, we construct an infinite family of $4$ -edge-critical $4$ -regular planar graphs which are fractionally $3$ -colorable. This disproves a conjecture of Gimbel, Kündgen, Li, and Thomassen (2019).

preprint2022arXiv

Erdős--Szekeres-type problems in the real projective plane

We consider point sets in the real projective plane $\mathbb{R}P^2$ 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 $\mathbb{R}P^2$ , which was initiated by Harborth and Möller in 1994. The notion of convex position in $\mathbb{R}P^2$ agrees with the definition of convex sets introduced by Steinitz in 1913. For $k \geq 3$ , an (\affine) $k$ -hole in a finite set $S \subseteq \mathbb{R}^2$ 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 $\mathbb{R}P^2$ , called projective $k$ -holes, we find arbitrarily large finite sets of points from $\mathbb{R}P^2$ with no \projective 8-holes, providing an analogue of a classical planar construction by Horton from 1983. We also prove that they contain only quadratically many \projective $k$ -holes for $k \leq 7$ . On the other hand, we show that the number of $k$ -holes can be substantially larger in~ $\mathbb{R}P^2$ than in $\mathbb{R}^2$ by constructing, for every $k \in \{3,\dots,6\}$ , sets of $n$ points from $\mathbb{R}^2 \subset \mathbb{R}P^2$ with $Ω(n^{3-3/5k})$ \projective $k$ -holes and only $O(n^2)$ \affine $k$ -holes. Last but not least, we prove several other results, for example about projective holes in random point sets in $\mathbb{R}P^2$ and about some algorithmic aspects. The study of extremal problems about point sets in $\mathbb{R}P^2$ opens a new area of research, which we support by posing several open problems.

preprint2022arXiv

Holes and islands in random point sets

For $d\in\mathbb{N}$ , let $S$ be a set of points in $\mathbb{R}^d$ in general position. A set $I$ of $k$ points from $S$ is a $k$ -island in $S$ if the convex hull $\mathrm{conv}(I)$ of $I$ satisfies $\mathrm{conv}(I) \cap S = I$ . A $k$ -island in $S$ in convex position is a $k$ -hole in $S$ . For $d,k\in\mathbb{N}$ and a convex body $K\subseteq\mathbb{R}^d$ of volume $1$ , let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$ . We show that the expected number of $k$ -holes in $S$ is in $O(n^d)$ . Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in $S$ by $2^{d-1}\cdot d!\cdot\binom{n}{d}$ . This is tight in the plane up to a lower-order term. Our method gives an asymptotically tight upper bound $O(n^d)$ even in the much more general setting, where we estimate the expected number of $k$ -islands in $S$ .

preprint2022arXiv

Tight bounds on the expected number of holes in random point sets

For integers $d \geq 2$ and $k \geq d+1$ , a $k$ -hole in a set $S$ of points in general position in $\mathbb{R}^d$ is a $k$ -tuple of points from $S$ in convex position such that the interior of their convex hull does not contain any point from $S$ . For a convex body $K \subseteq \mathbb{R}^d$ of unit $d$ -dimensional volume, we study the expected number $EH^K_{d,k}(n)$ of $k$ -holes in a set of $n$ points drawn uniformly and independently at random from $K$ . We prove an asymptotically tight lower bound on $EH^K_{d,k}(n)$ by showing that, for all fixed integers $d \geq 2$ and $k\geq d+1$ , the number $EH_{d,k}^K(n)$ is at least $Ω(n^d)$ . For some small holes, we even determine the leading constant $\lim_{n \to \infty}n^{-d}EH^K_{d,k}(n)$ exactly. We improve the currently best known lower bound on $\lim_{n \to \infty}n^{-d}EH^K_{d,d+1}(n)$ by Reitzner and Temesvari (2019). In the plane, we show that the constant $\lim_{n \to \infty}n^{-2}EH^K_{2,k}(n)$ is independent of $K$ for every fixed $k \geq 3$ and we compute it exactly for $k=4$ , improving earlier estimates by Fabila-Monroy, Huemer, and Mitsche (2015) and by the authors (2020).

preprint2020arXiv

A superlinear lower bound on the number of 5-holes

Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$ -hole in $P$ if $H$ is the vertex set of a convex $5$ -gon containing no other points of $P$ . For a positive integer $n$ , let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $Ω(n)$ and $O(n^2)$ , respectively. We show that $h_5(n) = Ω(n\log^{4/5}{n})$ , obtaining the first superlinear lower bound on $h_5(n)$ . The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $\ell$ into two subsets, each of size at least 5 and not in convex position, then $\ell$ intersects the convex hull of some 5-hole in $P$ . The proof of this result is computer-assisted.

preprint2020arXiv

Almost-equidistant sets

For a positive integer $d$ , a set of points in $d$ -dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let $f(d)$ denote the largest size of an almost-equidistant set in $d$ -space. It is known that $f(2)=7$ , $f(3)=10$ , and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that $f(5) \ge 16$ . We further show that $12\leq f(4)\leq 13$ , $f(5)\leq 20$ , $18\leq f(6)\leq 26$ , $20\leq f(7)\leq 34$ , and $f(9)\geq f(8)\geq 24$ . Up to dimension $7$ , our work is based on various computer searches, and in dimensions $6$ to $9$ , we give constructions based on the known construction for $d=5$ . For every dimension $d \ge 3$ , we give an example of an almost-equidistant set of $2d+4$ points in the $d$ -space and we prove the asymptotic upper bound $f(d) \le O(d^{3/2})$ .

preprint2020arXiv

Arrangements of Pseudocircles: On Circularizability

An arrangement of pseudocircles is a collection of simple closed curves on the sphere or in the plane such that any two of the curves are either disjoint or intersect in exactly two crossing points. We call an arrangement intersecting if every pair of pseudocircles intersects twice. An arrangement is circularizable if there is a combinatorially equivalent arrangement of circles. In this paper we present the results of the first thorough study of circularizability. We show that there are exactly four non-circularizable arrangements of 5 pseudocircles (one of them was known before). In the set of 2131 digon-free intersecting arrangements of 6 pseudocircles we identify the three non-circularizable examples. We also show non-circularizability of 8 additional arrangements of 6 pseudocircles which have a group of symmetries of size at least 4. Most of our non-circularizability proofs depend on incidence theorems like Miquel's. In other cases we contradict circularizability by considering a continuous deformation where the circles of an assumed circle representation grow or shrink in a controlled way. The claims that we have all non-circularizable arrangements with the given properties are based on a program that generated all arrangements up to a certain size. Given the complete lists of arrangements, we used heuristics to find circle representations. Examples where the heuristics failed were examined by hand.

preprint2020arXiv

Arrangements of Pseudocircles: Triangles and Drawings

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$ in digon-free arrangements of $n$ pairwise intersecting pseudocircles is at least $2n-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 with $p_3(\mathcal{A})/n \to 16/11 = 1.\overline{45}$ . We expect that the lower bound $p_3(\mathcal{A}) \geq 4n/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$ triangles. For pairwise intersecting arrangements with digons we have a lower bound of $p_3 \geq 2n/3$ , and conjecture that $p_3 \geq n-1$ . Concerning the maximum number of triangles in pairwise intersecting arrangements of pseudocircles, we show that $p_3 \le 2n^2/3 +O(n)$ . This is essentially best possible because there are families of pairwise intersecting arrangements of $n$ pseudocircles with $p_3/n^2 \to 2/3$ . 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.

preprint2020arXiv

On L-shaped point set embeddings of trees: first non-embeddable examples

An L-shaped embedding of a tree in a point set is a planar drawing of the tree where the vertices are mapped to distinct points and every edge is drawn as a sequence of two axis-aligned line segments. There has been considerable work on establishing upper bounds on the minimum cardinality of a point set to guarantee that any tree of the same size with maximum degree 4 admits an L-shaped embedding on the point set. However, no non-trivial lower bound is known to this date, i.e., no known $n$ -vertex tree requires more than $n$ points to be embedded. In this paper, we present the first examples of $n$ -vertex trees for $n\in\{13,14,16,17,18,19,20\}$ that require strictly more points than vertices to admit an L-shaped embedding. Moreover, using computer help, we show that every tree on $n\leq 12$ vertices admits an L-shaped embedding in every set of $n$ points. We also consider embedding ordered trees, where the cyclic order of the neighbors of each vertex in the embedding is prescribed. For this setting, we determine the smallest non-embeddable ordered tree on $n=10$ vertices, and we show that every ordered tree on $n\leq 9$ or $n=11$ vertices admits an L-shaped embedding in every set of $n$ points. We also construct an infinite family of ordered trees which do not always admit an L-shaped embedding, answering a question raised by Biedl, Chan, Derka, Jain, and Lubiw.

preprint2020arXiv

On the Average Complexity of the $k$ -Level

Let ${\cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The \emph{ $k$ -level} of ${\cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${\cal L}$ passing below $v$ . The complexity (the maximum size) of the $k$ -level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(n\cdot (k+1)^{1/3})$ . Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$ -level denotes the vertices at distance at most $k$ to a marked cell, the \emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$ -level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$ -spheres on the sphere $\mathbb{S}^d$ which are orthogonal to a set of random points on $\mathbb{S}^d$ . In this model, we prove that the expected complexity of the $k$ -level is of order $Θ((k+1)^{d-1})$ .

preprint2020arXiv

Two Disjoint 5-Holes in Point Sets

Given a set of points $S \subseteq \mathbb{R}^2$ , a subset $X \subseteq S$ with $|X|=k$ is called $k$ -gon if all points of $X$ lie on the boundary of the convex hull of $X$ , and $k$ -hole if, in addition, no point of $S \setminus X$ lies in the convex hull of $X$ . We use computer assistance to show that every set of 17 points in general position admits two disjoint 5-holes, that is, holes with disjoint respective convex hulls. This answers a question of Hosono and Urabe (2001). We also provide new bounds for three and more pairwise disjoint holes. In a recent article, Hosono and Urabe (2018) present new results on interior-disjoint holes -- a variant, which also has been investigated in the last two decades. Using our program, we show that every set of 15 points contains two interior-disjoint 5-holes. Moreover, our program can be used to verify that every set of 17 points contains a 6-gon within significantly smaller computation time than the original program by Szekeres and Peters (2006). Another independent verification of this result was done by Marić (2019).

preprint2016arXiv

Strongly Monotone Drawings of Planar Graphs

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 are based on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Manfred Scheucher

Research overview

Is this your work?

12 publications

Coloring circle arrangements: New $4$ -chromatic planar graphs

Erdős--Szekeres-type problems in the real projective plane

Holes and islands in random point sets

Tight bounds on the expected number of holes in random point sets

A superlinear lower bound on the number of 5-holes

Almost-equidistant sets

Arrangements of Pseudocircles: On Circularizability

Arrangements of Pseudocircles: Triangles and Drawings

On L-shaped point set embeddings of trees: first non-embeddable examples

On the Average Complexity of the $k$ -Level

Two Disjoint 5-Holes in Point Sets

Strongly Monotone Drawings of Planar Graphs

See the researcher in context

Building this map preview

Manfred Scheucher

Research overview

Is this your work?

12 publications

Coloring circle arrangements: New 444-chromatic planar graphs

Erdős--Szekeres-type problems in the real projective plane

Holes and islands in random point sets

Tight bounds on the expected number of holes in random point sets

A superlinear lower bound on the number of 5-holes

Almost-equidistant sets

Arrangements of Pseudocircles: On Circularizability

Arrangements of Pseudocircles: Triangles and Drawings

On L-shaped point set embeddings of trees: first non-embeddable examples

On the Average Complexity of the kkk-Level

Two Disjoint 5-Holes in Point Sets

Strongly Monotone Drawings of Planar Graphs

See the researcher in context

Building this map preview

Coloring circle arrangements: New $4$ -chromatic planar graphs

On the Average Complexity of the $k$ -Level