Here are some open problems (and one closed one) involving graphs and geometry that caught my attention at the EuroGIGA conference that I just attended.

Many attendees quickly became obsessed by Stefan Felsner's "beer problem": given a square array of numbers, find a tiling of a convex quadrilateral by smaller convex quadrilaterals, having the topology of the square grid, such that the area of each quadrilateral is the given number.

Felsner's beer problem

The general consensus seemed to be that it should always be possible to do this for \( 2\times n \) grids, although I don't think I saw a complete solution even for that case. For larger grid sizes, it's not possible to use degrees of freedom to rule out a solution, so maybe a solution always exists.

Sergio Cabello said during his talk "I don't know any nontrivial family of graphs for which deciding 1-planarity is polynomial". Here 1-planarity means that you can draw it in the plane in such a way that each edge is crossed at most once. And "nontrivial" should probably be taken to mean that it's a natural family of graphs for which the decision problem isn't trivially solvable; otherwise it's not hard to come up with contrived examples.

In Sasha Wolff's talk, he mentioned as an open problem the approximation of rectilinear Steiner arborescences in higher dimensions. Here one is given a set of points in three or more dimensions, and must find a set of line segments connecting them together. Each segment should be parallel to one of the coordinate axes, and every point in the network of segments (other than the origin) should be touched by a segment that extends towards the origin in one of the coordinate directions. The goal is to minimize the total length of the segments. A logarithmic approximation algorithm is known, but maybe constant is possible.

Csaba Tóth's invited talk covered quite a few open problems, including some famous ones, but the following one was new to me. If we are given a simple polygon with unit perimeter, and \( n \) circular disks with disjoint interiors, all touching the boundary of the polygon, how big can the sum of disk radii be, as a function of \( n \)? Toth stated a lower bound proportional to \( \log n / \log\log n \) and an upper bound proportional to \( \log n \), so there's still a nonconstant gap in what we know.

Finally, nearly three years ago I posted here a set of open problems that included one from Erdős: how many colors are needed to color a set of line segments, no three of which all cross each other? Now it has been solved: Oswin Aichholzer announced that the team of A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. Trotter, and B. Walczak have constructed triangle-free line segment arrangements that require arbitrarily large numbers of colors.