publications

2024

1. 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 Proceedings of the 2024 Symposium on Discrete Algorithms [SODA’24], 2024.

   Abs arXiv

   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 Proceedings of the 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 Proceedings of the 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 Proceedings of 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).