Open problem: Computing shortest pants decompositions
Description:
Explore optimal topological simplification of surfaces in this 47-minute lecture by Éric Colin de Verdière. Delve into algorithms and hardness results for economically simplifying surface topology, focusing on cutting surfaces along non-contractible or non-separating simple closed curves to reduce genus. Learn about the impact of cutting surfaces along graphs to create topological disks. Examine the search for shortest curves and graphs that simplify topology on surfaces with given metrics. Survey works by multiple authors, covering topics such as graphs on surfaces, properties of shortest non-trivial loops, surface topology in relation to graph theory, shortest cut graph results and algorithms, computation of overall shortest cut graphs, hard instances, and open problems in computing shortest pants decompositions.