Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Embedding Planar Graphs into Graphs of Treewidth
Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy +3
Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected distortion of -vertex planar graphs (with polynomial…
cs.CG2024
Optimal Euclidean Tree Covers
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
A of a metric space is a collection of trees, where every pair of points has a -stretch path in one of the trees. The…
cs.DS2024
Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
Hsien-Chih Chang, Jie Gao, Hung Le
Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted…