← All problems

Smallest Universal Set of Points for Planar Graphs

How many points must be placed in the plane to support planar drawing of all planar graphs on nn vertices? More precisely, call a set of points universal if every planar graph on nn vertices can be drawn with straight-line edges and without crossings by placing the vertices on a subset of the points. What is the smallest universal set of points as a function of nn? In particular, is it O(n)O(n)?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu