User Tools

Site Tools


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.

seminars/comb/abstract.201709dob.txt · Last modified: 2020/01/29 14:03 (external edit)