Date
Tue, 21 Nov 2023
Time
14:00 - 15:00
Location
L3
Speaker
Raphael Steiner
Organisation
ETH Zurich

In this talk, I will present new results addressing two rather well-known problems on the embeddability of planar graphs on point-sets in the plane. The first problem, often attributed to Mohar, asks for the asymptotics of the minimum size of so-called universal point sets, i.e. point sets that simultaneously allow straight-line embeddings of all planar graphs on n vertices. In the first half of the talk I will present a family of point sets of size O(n) that allow straight-line embeddings of a large family of n-vertex planar graphs, including all bipartite planar graphs. In the second half of the talk, I will present a family of (3+o(1))log2(n) planar graphs on n vertices that cannot be simultaneously embedded straight-line on a common set of n points in the plane. This significantly strengthens the previously best known exponential bound.

Last updated on 16 Nov 2023, 2:22pm. Please contact us with feedback and comments about this page.