Embedding planar graphs on point-sets: Problems and new results

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))\log_2(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.