Some Open Problems from 2018

Universal Point Sets for Planar Graphs

A planar point set is called $n$-universal if it allows simultaneous straight-line embeddings of all planar graphs on $n$ vertices.
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))

Orthogonal Symmetric Chain Decompositions: Shearer and Kleitman Conjecture

The $n$-cube is the poset obtained by ordering all subsets of $\{1,\ldots,n\}$ by inclusion. It is well-known that the $n$-cube can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ chains, which is the minimum possible number. Two such decompositions of the $n$-cube are called orthogonal if any two chains of the decompositions share at most a single element. Shearer and Kleitman conjectured in 1979 that the $n$-cube has $\lfloor n/2\rfloor+1$ pairwise orthogonal decompositions into the minimum number of chains, and they constructed two such decompositions.
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.

However, Shearer and Kleitman's Conjecture remains open.

L-shaped Point Set Embeddings of Trees

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.
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.

Deciding Circularizability of Arrangements of Pseudocircles

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 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.

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.
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.

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.
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$.

The precise values $f(d)$ for $d \ge 4$ are not known.
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.

Triangles in Arrangements of Pseudocircles: Weak Grünbaum Conjecture

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 (1972), 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$.
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$.

Number of 5-Holes in Planar Point Sets

Consider a finite set of points $P$ in the plane where no three points lie on a common line. A set of five points from $P$ is a $5$-hole if it is the vertex set of a convex pentagon containing no other points of $P$. It is widely conjectured that the number of 5-holes is $\Omega(n^2)$, where $n$ is the number of points in the point set.
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

contains a $5$-hole which is spanned by points from both, $A$ and $B$.
We wonder whether this more general theorem can also be used to show a lower bound of $\Omega(n^c)$ for some $c>1$.

Strongly Monotone Drawings of Biconnected 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.
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.