Research Projects

Most of my active research projects are about planar metrics. What property does planar metrics have that makes them special? What advantages can we take to construct better and more efficient algorithms? Can we represent planar metrics in succinct forms, while preserving the distances exactly or approximately?

emulator for Monge matrix
Distance-Preserving Structures for Planar Metrics

Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More,
with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
SODA 2024.
Covering Planar Metrics and Beyond by O(1) Trees,
with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
FOCS 2023.
Near-Linear ε-Emulators for Planar Graphs,
with Robert Krauthgamer and Zihan Tan,
STOC 2022.

scattering partition of string graph
Optimation Problem on Geometric Intersection Graphs

Charting the Diameter Computation Landscape of Intersection Graphs in Three and Higher Dimensions,
with Timothy M. Chan, Jie Gao, Hung Le, Sándor Kisfaludi-Bak, David Zheng,
SOCG 2026.
Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support,
with Reilly Browne,
SOCG 2026.
Cutting Planarians: Planar Emulators for String Graphs,
with Jonathan Conroy, Zihan Tan, David Zheng,
STOC 2026.
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension,
with Timothy M. Chan, Jie Gao, Hung Le, Sándor Kisfaludi-Bak, David Zheng,
FOCS 2025.

depth contours
Curves and Graphs on Surfaces

From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy,
with Brittany Terese Fasy, Bradley McCoy, David L. Millman, and Carola Wenk,
WADS 2023.
Untangling Planar Graphs and Curves by Staying Positive,
with Santiago Aranguri and Dylan Fridman,
SODA 2022.
Tightening Curves on Surfaces Monotonically with Applications,
with Arnaud de Mesmay,
SODA 2020.

compressed graph from hierarchical covering
Efficient Optimization in Euclidean Spaces

Optimal Euclidean Tree Covers,
with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
SoCG 2024.
Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching,
with Pankaj Agarwal, Sharath Raghvendra and Allen Xiao,
STOC 2022.
Dynamic Geometric Set Cover and Hitting Set,
with Pankaj Agarwal, Subhash Suri, Allen Xiao, and Jie Xue,
SoCG 2020.

← Back to Main Page

last modified on

	Distance-Preserving Structures for Planar Metrics Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More, with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than, SODA 2024. Covering Planar Metrics and Beyond by O(1) Trees, with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than, FOCS 2023. Near-Linear ε-Emulators for Planar Graphs, with Robert Krauthgamer and Zihan Tan, STOC 2022.
	Optimation Problem on Geometric Intersection Graphs Charting the Diameter Computation Landscape of Intersection Graphs in Three and Higher Dimensions, with Timothy M. Chan, Jie Gao, Hung Le, Sándor Kisfaludi-Bak, David Zheng, SOCG 2026. Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support, with Reilly Browne, SOCG 2026. Cutting Planarians: Planar Emulators for String Graphs, with Jonathan Conroy, Zihan Tan, David Zheng, STOC 2026. Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension, with Timothy M. Chan, Jie Gao, Hung Le, Sándor Kisfaludi-Bak, David Zheng, FOCS 2025.
	Curves and Graphs on Surfaces From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy, with Brittany Terese Fasy, Bradley McCoy, David L. Millman, and Carola Wenk, WADS 2023. Untangling Planar Graphs and Curves by Staying Positive, with Santiago Aranguri and Dylan Fridman, SODA 2022. Tightening Curves on Surfaces Monotonically with Applications, with Arnaud de Mesmay, SODA 2020.
	Efficient Optimization in Euclidean Spaces Optimal Euclidean Tree Covers, with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than, SoCG 2024. Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching, with Pankaj Agarwal, Sharath Raghvendra and Allen Xiao, STOC 2022. Dynamic Geometric Set Cover and Hitting Set, with Pankaj Agarwal, Subhash Suri, Allen Xiao, and Jie Xue, SoCG 2020.