Andreas E. Feldmann - A -embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs

Explore a 27-minute lecture by Andreas Emil Feldmann on embedding low highway dimension graphs into bounded treewidth graphs. Delve into the concept of graphs with bounded highway dimension as a model for transportation networks. Learn about a novel embedding technique that distorts distances by a factor of 1+ε in expectation while achieving polylogarithmic treewidth. Discover how this result leads to quasi-polynomial time approximation schemes for optimization problems in transportation networks. Examine the extension of Talwar's embedding techniques for low doubling dimension metrics and the analysis of low highway dimension graph structures. Gain insights into the application of geometric tools beyond low doubling metrics. Follow the lecture's progression from introduction to formal definitions, embedding construction, proofs, and conclusions, including discussions on air traffic networks and open problems in the field.