5 citations · 27 across the 31 of their papers we have counts for
5 papers · 1 filter
Greedy spanners are optimal in doubling metrics
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
We show that the greedy spanner algorithm constructs a -spanner of weight for a point set in metrics of doubling dimension , resolving an open…
Minor-free graphs have light spanners
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
We show that every -minor-free graph has a light -spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung. Our lightness bou…
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…
Light spanners for bounded treewidth graphs imply light spanners for -minor-free graphs
Glencora Borradaile, Hung Le
Grigni and Hung~\cite{GH12} conjectured that H-minor-free graphs have -spanners that are light, that is, of weight times the weight of the minimum spanning tree f…
Embedded-width: A variant of treewidth for plane graphs
Glencora Borradaile, Jeff Erickson, Hung Le +1
We define a special case of tree decompositions for planar graphs that respect a given embedding of the graph. We study the analogous width of the resulting decomposition we call t…