6 papers · 1 filter
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…
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…
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…