11 papers
Metric Planarity Testing is Hard
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…
Peeling Half the Onion: Embedding -Outerplanar Graphs into and Trees with a Polynomial Distortion (in )
Hsien-Chih Chang, Jonathan Conroy, William Eliot +2
Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that -outerplanar graphs can be embedded into trees and with distortion . Their result is pe…
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainl…
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms…
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
We give the first truly subquadratic time algorithm, with running time, for computing the diameter of an -vertex unit-disk graph, resolving a central open prob…
Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Hsien-Chih Chang, Jonathan Conroy, Hung Le +2
A -stretch tree cover of an edge-weighted -vertex graph is a collection of trees, where every pair of vertices has a -stretch path in one o…
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…
Towards Instance-Optimal Euclidean Spanners
Hung Le, Shay Solomon, Cuong Than +2
Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic "compactness'' measures of a Euclidean spanner are the…
Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii +4
We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant , one could constru…
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…
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…