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.

Introduction
Low highway dimension graphs
Why would I mention
What we were interested in
Formal definition
Embedding
Results
Construction
Hierarchy
Decomposition
SubTowns
Doubling Dimension
Core Hubs
Proof
Properties
Similarities
Method
Issues
A definition
Conclusions
Air traffic networks
Open problems