Publications

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

Graph Theory and Algorithms

• Computing Diameter+2 in Truly Subquadratic Time for Unit-Disk Graphs,
  with Hung Le, Jie Gao,
  accepted to SOCG 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,
  accepted to SODA 2024.

• 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 by O(1) Trees,
  with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
  accepted to FOCS 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.