Combinatorics Seminar: "Homotopy height in a graph"

Speaker: Erin Chambers, Saint Louis University

Abstract: Homotopy height is a parameter quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves γ1 and γ2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between γ1 and γ2 where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems.  In this talk, we will investigate the structure of optimal homotopies under homotopy height, and then connect the parameter to known parameters such as the pathwidth and the outer-planarity of a graph.  Finally, we will connect homotopy height to the height of a graph drawing and show that homotopy height gives lower bounds on the straight-line drawing height that are never worse than the ones obtained from pathwidth and outer-planarity.

Host: Martha Precup