In A Note On Universal Point Sets for Planar Graphs we show that any $n$-universal set has at least $(1.293-o(1))n$ points (this improves the previous best constant $1.235$ by Kurowski (2004)) and we provide a set of 23 planar 11-vertex graphs which cannot be simultaneously drawn on any set of 11 points (this strengthens a result by Cardinal, Hoffmann, and Kusters (2015)). The smallest $n$-universal sets known at this date, however, remain of quadratic size.

- What is the minimal size of an $n$-universal set? In particular, is there a superlinear lower bound on the number of points for $n$-universal sets, and are there $n$-universal sets of sub-quadratic size?
- Can every two planar graphs be drawn simultaneously on a point set? (A question by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw, and Mitchell (2007))

In On orthogonal symmetric chain decompositions we provide the currently best known bounds by constructing

- four pairwise orthogonal chain decompositions of the $n$-cube for $n\geq 60$ and
- five pairwise edge-disjoint chain decompositions of the $n$-cube for $n\geq 90$, where edge-disjointness is a slightly weaker notion than orthogonality.

In On L-shaped point set embeddings of trees: first non-embeddable examples 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. For the more restrictive setting, where the cyclic order of the neighbors of each vertex in the embedding is prescribed, we construct an infinite family of ordered trees which do not always admit an L-shaped embedding on $n$ points.

- We conjecture that our infinite family does not always admit an L-shaped embedding, even when the cyclic order is not prescribed.
- Since all non-embeddable examples that we know are trees with pathwidth 2 (lobsters), it would be interesting to know whether trees with pathwidth 1 (caterpillars) always admit an L-shaped embedding.
- All known nonembeddable trees have maximum degree 4, so the question for trees with maximum degree 3 remains open.
- Also the question, whether any set of n points is always sufficient to guarantee an orthogeodesic embedding of any n-vertex tree, remains open.

In Arrangements of Pseudocircles: On Circularizability 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) and
- in the set of 2131 digon-free intersecting arrangements of 6 pseudocircles we identify the three non-circularizable examples.

To classify arrangements as non-circularizable in a more quantitative way, it would be nice to have an algorithm for deciding circularizability which is practical. In the case of stretchability of arrangements of pseudolines, the method based on final polynomials, i.e., on the Graßmann-Plücker relations, would qualify as being practical.

In Almost-equidistant sets we give independent, computer-assisted proofs of these statements and further show that

- $12\leq f(4)\leq 13$,
- $16 \le f(5)\leq 20$,
- $18\leq f(6)\leq 26$,
- $20\leq f(7)\leq 34$, and
- $f(9)\geq f(8)\geq 24$.

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})$. This bound was further improved to $O(n^{4/3})$ (see arxiv:1708.01590 and arxiv:1708.02039), but the exact asymptotics remain unknown.

In Arrangements of Pseudocircles: Triangles and Drawings we present examples to disprove Grünbaum's 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.
- We conjecture 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$.

In A superlinear lower bound on the number of 5-holes we have shown that the number of 5-holes is at least $\Omega(n \log^{4/5} n)$. Towards this theorem we have proven a more general theorem, which asserts that every point set $P=A \cup B$ with

- $A$ and $B$ separated by a line $\ell$,
- $|A|,|B| \ge 5$, and
- $A$ and $B$ both not in convex position

We wonder whether this more general theorem can also be used to show a lower bound of $\Omega(n^c)$ for some $c>1$.

In Strongly Monotone Drawings of Planar Graphs we have shown that every 3-connected planar graph admits a strongly monotone drawing, while there exist 1-connected planar graphs which do not. The question for 2-connected planar graphs remains open. Last update: December 19 2018 12:15:18.