publications

2025

1. Embedding Planar Graphs into Graphs of Treewidth \(O(\log^3 n)\)

   with Hsien-Chih Chang, Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, and Michał Pilipczuk

   in 2025 Symposium on Discrete Algorithms [SODA’25], 2025.

   Abs arXiv

   Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected \(1+\varepsilon\) distortion of n-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth \(O(\varepsilon^−1 \log^13 n) \). Their embedding is the first to achieve polylogarithmic treewidth. However, there remains a large gap between the treewidth of their embedding and the treewidth lower bound of \(Ω(\log n)\) shown by Carroll and Goel [CG04]. In this work, we substantially narrow the gap by constructing a stochastic embedding with treewidth \(O(\varepsilon^-1 \log^3 n) \).

   We obtain our embedding by improving various steps in the CLPP construction. First, we streamline their embedding construction by showing that one can construct a low-treewidth embedding for any graph from (i) a stochastic hierarchy of clusters and (ii) a stochastic balanced cut. We shave off some logarithmic factors in this step by using a single hierarchy of clusters. Next, we construct a stochastic hierarchy of clusters with optimal separating probability and hop bound based on shortcut partition [CCLMST23, CCLMST24]. Finally, we construct a stochastic balanced cut with an improved trade-off between the cut size and the number of cuts. This is done by a new analysis of the contraction sequence introduced by [CLPP23]; our analysis gives an optimal treewidth bound for graphs admitting a contraction sequence.

2024

1. Optimal Euclidean Tree Covers

   with Hsien-Chih Chang, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than

   in 40th International Symposium on Computational Geometry [SoCG’24], 2024.

   Invited to DCG special issue.

   Abs arXiv

   A \((1+\varepsilon)\)-stretch tree cover of a metric space is a collection of trees, where every pair of points has a \((1+\varepsilon)\)-stretch path in one of the trees. The celebrated Dumbbell Theorem [Arya et. al., STOC’95] states that any set of \(n\) points in \(d\)-dimensional Euclidean space admits a \((1+\varepsilon)\)-stretch tree cover with \(O_d(\varepsilon^{-d} ⋅\log(1/\varepsilon))\) trees, where the \(O_d\) notation suppresses terms that depend solely on the dimension \(d\). The running time of their construction is \(O_d(n \log n ⋅\frac{\log(1/\varepsilon)}{\varepsilon^d} + n ⋅\varepsilon^{-2d})\). Since the same point may occur in multiple levels of the tree, the maximum degree of a point in the tree cover may be as large as \(Ω(\log Φ)\), where \(Φ\) is the aspect ratio of the input point set.

   In this work we present a \((1+\varepsilon)\)-stretch tree cover with \(O_d(\varepsilon^{-d+1} ⋅\log(1/\varepsilon))\) trees, which is optimal (up to the \(\log(1/\varepsilon)\) factor). Moreover, the maximum degree of points in any tree is an absolute constant for any \(d\). As a direct corollary, we obtain an optimal routing scheme in low-dimensional Euclidean spaces. We also present a \((1+\varepsilon)\)-stretch Steiner tree cover (that may use Steiner points) with \(O_d(\varepsilon^{(-d+1)/2} ⋅\log(1/\varepsilon))\) trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive \(O_d(n \log n)\) term; this improves over the running time underlying the Dumbbell Theorem.

2. Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More

   with Hsien-Chih Chang, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than

   in 2024 Symposium on Discrete Algorithms [SODA’24], 2024.

   Abs arXiv Slides

   The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCL+23], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices u and v in the graph, there exists a path between \(u\) and \(v\) that intersects only a few clusters. They proved that any planar graph admits a shortcut partition and gave several applications, including a construction of tree cover for arbitrary planar graphs with stretch \(1+\varepsilon\) and O(1) many trees for any fixed \(\varepsilon ∈(0, 1)\). However, the construction heavily exploits planarity in multiple steps, and is thus inherently limited to planar graphs.

   In this work, we breach the “planarity barrier” to construct a shortcut partition for \(K_r\)-minor-free graphs for any \(r\). To this end, we take a completely different approach — our key contribution is a novel deterministic variant of the cop decomposition in minor-free graphs [And86, AGG+14]. Our shortcut partition for \(K_r\) -minor-free graphs yields several direct applications. Most notably, we construct the first optimal distance oracle for \(K_r\)-minor-free graphs, with \(1 + \varepsilon\)stretch, linear space, and constant query time for any fixed \(\varepsilon ∈(0, 1)\). The previous best distance oracle [AG06] uses \(O(n \log n)\) space and \(O(\log n)\)query time, and its construction relies on Robertson-Seymour structural theorem and other sophisticated tools. We also obtain the first tree cover of \(O(1)\) size for minor-free graphs with stretch \(1 + \varepsilon\), while the previous best \((1 + \varepsilon)\)-tree cover has size \(O(\log^2 n)\) [BFN19].

   As a highlight of our work, we employ our shortcut partition to resolve a major open problem — the Steiner point removal (SPR) problem: Given any set \(K\) of terminals in an arbitrary edge-weighted planar graph \(G\), is it possible to construct a minor \(M\) of \(G\) whose vertex set is \(K\), which preserves the shortest-path distances between all pairs of terminals in \(G\) up to a constant factor? Positive answers to the SPR problem were only known for very restricted classes of planar graphs: trees [Gup01], outerplanar graphs [BG08], and series-parallel graphs [HL22]. We resolve the SPR problem in the affirmative for any planar graph, and more generally for any \(K_r\)-minor-free graph for any fixed \(r\). To achieve this result, we prove the following general reduction and combine it with our new shortcut partition: For any graph family closed under taking subgraphs, the existence of a shortcut partition yields a positive solution to the SPR problem.

2023

1. Covering Planar Metrics (and Beyond): O(1) Trees Suffice

   with Hsien-Chih Chang, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than

   in 64th Symposium on Foundations of Computer Science [FOCS’23], 2023.

   Abs arXiv Slides

   While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics. Specifically, a tree cover of a metric space \((X, δ)\) is a collection of trees, so that every pair of points \(u\) and \(v\) in \(X\) has a low-distortion path in at least one of the trees.

   The celebrated “Dumbbell Theorem” [ADMSS95] states that any low-dimensional Euclidean space admits a tree cover with \(O(1)\) trees and distortion \(1+\varepsilon\), for any fixed \(\varepsilon ∈(0,1)\). This result has found numerous algorithmic applications, and has been generalized to the wider family of doubling metrics [BFN19]. Does the same result hold for planar metrics? A positive answer would add another evidence to the well-observed connection between Euclidean/doubling metrics and planar metrics.

   In this work, we answer this fundamental question affirmatively. Specifically, we show that for any given fixed \(\varepsilon ∈(0,1)\), any planar metric can be covered by \(O(1)\) trees with distortion \(1+\varepsilon\). Our result for planar metrics follows from a rather general framework: First we reduce the problem to constructing tree covers with additive distortion . Then we introduce the notion of shortcut partition , and draw connection between shortcut partition and additive tree cover. Finally we prove the existence of shortcut partition for any planar metric, using new insights regarding the grid-like structure of planar graphs. To demonstrate the power of our framework:

   • We establish additional tree cover results beyond planar metrics; in particular, we present an \(O(1)\)-size tree cover with distortion \(1+\varepsilon\) for bounded treewidth metrics;
   • We obtain several algorithmic applications in planar graphs from our tree cover.

   The grid-like structure is a technical contribution that we believe is of independent interest. We showcase its applicability beyond tree cover by constructing a simpler and better embedding of planar graphs into \(O(1)\)-treewidth graphs with small additive distortion, resolving an open problem in this line of research.

2022

1. Hop-Spanners for Geometric Intersection Graphs

   with Csaba Tóth

   in 38th International Symposium on Computational Geometry [SoCG’22], 2022.

   Invited to JoCG special issue.

   Abs arXiv Slides

   A \(t\)-spanner of a graph \(G=(V,E)\) is a subgraph \(H=(V,E’)\) that contains a \(uv\)-path of length at most \(t\) for every \(uv∈E\). It is known that every \(n\)-vertex graph admits a \((2k-1)\)-spanner with \(O(n^1+1/k)\) edges for \(k≥1\). This bound is the best possible for \(1≤k≤9\) and is conjectured to be optimal due to Erdős’ girth conjecture. We study \(t\)-spanners for \(t∈{2,3}\) for geometric intersection graphs in the plane. These spanners are also known as \(t\)-hop spanners to emphasize the use of graph-theoretic distances (as opposed to Euclidean distances between the geometric objects or their centers). We obtain the following results: (1) Every \(n\)-vertex unit disk graph (UDG) admits a 2-hop spanner with \(O(n)\) edges; improving upon the previous bound of \(O(n\log n)\). (2) The intersection graph of \(n\) axis-aligned fat rectangles admits a 2-hop spanner with \(O(n\log n)\) edges, and this bound is the best possible. (3) The intersection graph of \(n\) fat convex bodies in the plane admits a 3-hop spanner with \(O(n\log n)\) edges. (4) The intersection graph of \(n\) axis-aligned rectangles admits a 3-hop spanner with \(O(n\log^2 n)\) edges.

2021

1. Robot Development and Path Planning for Indoor Ultraviolet Light Disinfection

   with Christopher Thierauf, Parker Rule, Evan A. Krause, Hugo Alves Akitaya, Andrei Gonczi, Matias Korman, and Matthias Scheutz

   in the 2021 IEEE International Conference on Robotics and Automation [ICRA’21], 2021.

   Abs arXiv Code Slides

   Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems attempting to automate it suffer from high costs and inefficient irradiation. In this paper, we propose a purpose-made inexpensive robotic platform with off-the-shelf components and stan- dard navigation software that, with a novel algorithm for finding optimal irradiation locations, addresses both shortcomings to offer affordable and efficient solutions for UVC irradiation. We demonstrate in simulations the efficacy of the algorithm and show a prototypical run of the autonomous integrated robotic system in an indoor environment. In our sample instances, our proposed algorithm reduces the time needed by roughly 30% while it increases the coverage by a factor of 35% (when compared to the best possible placement of a static light).