====== Michael Dobbins (Binghamton) ======

====== Area-Universal Graphs and Some "Universal-Existential-Real"–Hard Problems ======

===== Abstract for the Combinatorics Seminar 2017 October 3 =====

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.


----