An exponential bound for simultaneous embeddings of planar graphs

Abstract

We show that there are $O(n\cdot 4^{n/11})$ planar graphs on $n$ vertices which do not admit a simultaneous straight-line embedding on any $n$-point set in the plane. In particular, this improves the best known bound $O(n!)$ significantly.

4 figures, 8 pages