Problem of the Week
Hilton Memorial Lecture
A planar drawing of a graph is area universal when, for every assignment of positive real values to the faces, there is a redrawing of the graph that realizes the given face areas. The complexity of deciding whether a given planar drawing is area universal is unknown. This problem is in the universal-existential-real complexity class (UER), which consists of problems that can be reduced in polynomial time to deciding whether a given algebraic formula has a real solution, and it may be a natural candidate for a complete problem in this class.
I will describe some variants of this problem, and related problems that are UER-complete problems.
This is joint work with Linda Kleist, Tillmann Miltzow, and Pawel Rzazewski.