**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

You are here: Homepage » Seminars - Academic year 2022-23 » Combinatorics Seminar » Michael Dobbins (Binghamton)

seminars:comb:abstract.201709dob

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)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported