Monday, July 10, 2017
Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
PPAD and PLS are two prominent complexity classes
of search problems that lie between FP and TFNP.
So far, they have been studied mostly from the
perspective of computational game theory, but recently
there were several results that relate them to problems
from discrete geometry, such as the Tverberg problem or
the colorful Caratheodory problem.
The talk will give a broad overview of these complexity
classes and their context, as well as some recent
developments.
Based on joint work with Frederic Meunier, Pauline Sarrabezolles, and
Yannik Stein.
Colloquium - 16:00
Abstract:
We introduce and study the problem Ordered Level Planarity which asks for
a planar drawing of a graph such that vertices are placed at prescribed
positions in the plane and such that every edge is realized as a
y-monotone curve. This can be interpreted as a variant of Level Planarity
in which the vertices on each level appear in a prescribed total order. We
establish a complexity dichotomy with respect to both the maximum degree
and the level-width, that is, the maximum number of vertices that share a
level / y-coordinate. Our study of Ordered Level Planarity is motivated by
connections to several other graph drawing problems.
Orthogeodesic Planarity asks for a planar drawing of a graph G such that
vertices are placed at prescribed positions in the plane and such that
every edge e is realized as a rectilinear L_1-geodesic path. Katz, Krug,
Rutter and Wolff claimed that this problem can be solved in polynomial
time if G is a matching. Via a reduction from Ordered Level Planarity, we
show that this claim is incorrect unless P=NP. Our reduction extends to
settle the complexity of the Bi-Monotonicity problem, which was proposed
by Fulek, Pelsmajer, Schaefer and Stefankovic. We also established Ordered
Level Planarity as a special case of several other Level Planarity
variants and, thus, strengthen previous hardness results.
(joint work with Günter Rote)