Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 24, 2022, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Eleonora Eichelberg
Counting crossing-free structures on a given point set, in particular triangulations, is a well-known problem. Yet its computational complexity is mostly unknown. In this talk we consider variants of the problem in which we impose conditions on the edge set: either by forbidding edges (so called restricted counting problems) or by requiring edges (so called augmented counting problems). We present some #P-completeness results in this setting and show by the example of counting restricted cycle covers how such results may be obtained by reducing planar #3-SAT.
Automatic MiSe System Software Version 1.4803M | admin login