Publications

Sort by Time / Sort by Subject

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.

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.

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.

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.

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.

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.

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

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).

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.

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.

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.

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

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".

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".

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

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".

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.

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.

Asymptotically Optimal Thickness Bounds of Generalized Bar Visibility Graphs,
with Yen-Peng Sung and Hsueh-I Lu,
manuscript not intended for publication, 2009.

← Back to Main Page

last modified on

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.
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.
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.
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.
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.
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.
Planar Emulators for Monge Matrices, with Tim Ophelders, in Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG'20), pages 141-147, 2020.
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).
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.
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.
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.
Tightening Curves and Graphs on Surfaces, Ph.D. dissertation, University of Illinois at Urbana-Champaign, July 2018.
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".
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".
Invertibility and Largest Eigenvalue of Symmetric Matrix Signings, with Charles Carlson, Karthekeyan Chandrasekaran, and Alexandra Kolla, Preprint, 2017.
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".
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.
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.
Asymptotically Optimal Thickness Bounds of Generalized Bar Visibility Graphs, with Yen-Peng Sung and Hsueh-I Lu, manuscript not intended for publication, 2009.