5 papers
Fatness and Flatness
Arnold Filtser, Hung Le, Nikolas Mählmann +2
Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of s…
A Separator for Minor-Free Graphs Beyond the Flow Barrier
Hung Le
In 1990, Alon, Seymour, and Thomas gave the first balanced separator of size for any -minor-free graph, which has had numerous algorithmic applications. T…
Coarse Balanced Separators in Fat-Minor-Free Graphs
Ãdouard Bonnet, Hung Le, Marcin Pilipczuk +1
Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just b…
Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
Glencora Borradaile, Hung Le, Melissa Sherman-Bennett
Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has a…
Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
Hung Le, Shay Solomon
Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graph…