Publications

Graph Theory and Algorithms

• 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,
  accepted to SOCG 2026.

• Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support,
  with Reilly Browne,
  accepted to SOCG 2026.

• Cutting Planarians: Planar Emulators for String Graphs,
  with Jonathan Conroy, Zihan Tan, David Zheng,
  accepted to STOC 2026.
  This paper is the full version of (and improves over the results from) our earlier preprint "O(1)-Distortion Planar Emulators for String Graphs".

• O(1)-Distortion Planar Emulators for String Graphs,
  with Jonathan Conroy, Zihan Tan, David Zheng,
  manuscript.

• 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,
  accepted to FOCS 2025.

• Distance Approximating Minors for Planar and Minor-Free Graphs,
  with Jonathan Conroy,
  accepted to FOCS 2025.

• Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs,
  with Jonathan Conroy, Hung Le, Shay Solomon, Cuong Than,
  accepted to STOC 2025.

• Embedding Planar Graphs into Graphs of Treewidth $O(\log^3 n)$,
  with Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michał Pilipczuk,
  accepted to SODA 2025.

• Computing Diameter+2 in Truly Subquadratic Time for Unit-Disk Graphs,
  with Hung Le, Jie Gao,
  in Proceedings of the 40th International Symposium on Computational Geometry (SoCG 2024),
  pages 38:1-38:14, 2024.

• 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,
  in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024),
  pages 5300-5331, 2024.
  This paper improves over the results from our earlier preprint "Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions".

• Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions,
  with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
  manuscript, 2023.

• Covering Planar Metrics (and Beyond): O(1) Trees Suffice,
  with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
  in Proceedings of the IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023),
  pages 2231-2261, 2023.

• Near-Linear ε-Emulators for Planar Graphs,
  with Robert Krauthgamer and Zihan Tan,
  in Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC'22),
  pages 1311–1324, 2022.

• Planar Emulators for Monge Matrices,
  with Tim Ophelders,
  in Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG'20),
  pages 141-147, 2020.

• Near-Optimal Distance Emulator for Planar Graphs,
  with Paweł Gawrychowski, Shay Mozes, and Oren Weimann,
  in Proceedings of the 26th Annual European Symposium on Algorithms (ESA'18),
  pages 16:1-16:17, 2018.

• Spectral Aspects of Symmetric Matrix Signings,
  with Charles Carlson, Karthekeyan Chandrasekaran, Naonori Kakimura, and Alexandra Kolla,
  Discrete Optimization, volume 37, article 100582, pages 1-22, 2020.
  Conference version in Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS'19),
  pages 81:1-81:13, 2019.
  This paper improves over some of the results from our earlier preprint "Invertibility and Largest Eigenvalue of Symmetric Matrix Signings".
  

• Invertibility and Largest Eigenvalue of Symmetric Matrix Signings,
  with Charles Carlson, Karthekeyan Chandrasekaran, and Alexandra Kolla,
  Preprint, 2017.

• A Faster Algorithm to Recognize Even-Hole-Free Graphs,
  with Hsueh-I Lu,
  Journal of Combinatorial Theory, Series B, volume 113, pages 141-161, 2015.
  Conference version in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12),
  pages 1286-1297, 2012.
  

• Computing the Girth of a Planar Graph in Linear Time,
  with Hsueh-I Lu,
  SIAM Journal on Computing 42(3), pages 1077-1094, 2013.
  Conference version in Proceedings of the 17th International Computing and Combinatorics Conference (COCOON'11),
  Lecture Notes in Computer Science 6842, pages 225-236, 2011.

Computational Topology

• 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,
  in Proceedings of the 18th Algorithms and Data Structures Symposium (WADS'23),
  pages 605–619, 2023.

• Untangling Planar Graphs and Curves by Staying Positive,
  with Santiago Aranguri and Dylan Fridman,
  in Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'22),
  pages 211-225, 2022.

• Hard Diagrams of the Unknot,
  with Benjamin A. Burton, Maarten Löffler, Arnaud de Mesmay, Clément Maria, Saul Schleimer, Eric Sedgwick, Jonathan Spreer,
  manuscript.

• Tightening Curves on Surfaces Monotonically with Applications,
  with Arnaud de Mesmay,
  in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20),
  pages 747-766, 2020.
  Invited to special issue of the ACM Transactions on Algorithms (TALG).

• Lower Bounds for Electrical Reduction on Surfaces,
  with Marcos Cossarini and Jeff Erickson,
  in Proceedings of the 35th International Symposium on Computational Geometry (SoCG'19),
  pages 25:1-25:16, 2019.
  

• Tightening Curves and Graphs on Surfaces,
  Ph.D. dissertation, University of Illinois at Urbana-Champaign, July 2018.

• Tightening Curves on Surfaces via Local Moves,
  with Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, and Stephan Tillmann,
  Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'18),
  pages 121-135, 2018.

• Lower Bounds for Planar Electrical Reduction,
  with Jeff Erickson,
  preprint, 2017.

• Unwinding Annular Curves and Electrically Reducing Planar Networks,
  with Jeff Erickson,
  Extended abstract appeared in Computational Geometry: Young Researchers Forum from the
  33rd International Symposium on Computational Geometry (SoCG'17), 2017.
  Results from this paper has been split and extended in two separate papers "Lower Bounds for Planar Electrical Reduction" and "Tightening Curves on Surfaces via Local Moves".

• Untangling Planar Curves,
  with Jeff Erickson,
  Discrete & Computational Geometry, volume 58, issue 4, pages 889-920, 2017.
  Special issue of invited papers from the 32nd International Symposium on Computational Geometry (SoCG'16).
  Conference version in Proceedings of the 32nd International Symposium on Computational Geometry (SoCG'16),
  pages 29:1-29:16, 2016.
  This paper improves over some of the results from our earlier preprint "Electrical Reduction, Homotopy Moves, and Defect".
  Won the best student presentation award! Here are the slides.
  

• Electrical Reduction, Homotopy Moves, and Defect,
  with Jeff Erickson,
  preprint, 2015.
  Some of the results from this paper are being improved in our conference submission "Untangling planar curves".
  

Computational Geometry

• Optimal Euclidean Tree Covers,
  with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
  in Proceedings of the 40th International Symposium on Computational Geometry (SoCG 2024),
  pages 37:1-37:15, 2024.

• Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching,
  with Pankaj Agarwal, Sharath Raghvendra and Allen Xiao,
  in Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC'22),
  pages 1052–1065, 2022.

• Clustering under Perturbation Stability in Near-Linear Time,
  with Pankaj Agarwal, Kamesh Munagala, Erin Taylor, and Emo Welzl,
  in 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'20),
  pages 8:1-8:16, 2020.

• Dynamic Geometric Set Cover and Hitting Set,
  with Pankaj Agarwal, Subhash Suri, Allen Xiao, and Jie Xue,
  in 36th International Symposium on Computational Geometry (SoCG'20),
  pages 2:1-2:15, 2020.

• Efficient Algorithms for Geometric Partial Matching,
  with Pankaj Agarwal and Allen Xiao,
  in Proceedings of the 35th International Symposium on Computational Geometry (SoCG'19),
  pages 6:1-6:14, 2019.
  

• Detecting Weakly Simple Polygons,
  with Jeff Erickson and Chao Xu,
  in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15),
  pages 1655-1670, 2015.
  

• From Proximity to Utility: A Voronoi Partition of Pareto Optima,
  with Sariel Har-Peled and Benjamin Raichel,
  Discrete & Computational Geometry, volume 56, issue 3, pages 631-656, 2016.
  Conference version in Proceedings of the 31st International Symposium on Computational Geometry (SoCG'15),
  pages 689-703, 2015.