TZTianyi Zhang

Tianyi Zhang

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Tianyi Zhang has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Covering the Euclidean Plane by a Pair of Trees

    by Hung Le, Lazar Milenković, Shay Solomon, Tianyi Zhang

    A {$t$-stretch tree cover} of a metric space $M = (X,δ)$, for a parameter $t \ge 1$, is a collection of trees such that every pair of points has a $t$-stretch path in one of the trees. Tree covers provide an important sketching tool that has found various applications over the years. The celebrated {Dumbbell Theorem} by Arya et al. [STOC'95] states that any set of points in the Euclidean plane admits a $(1+ε)$-stretch tree cover with $O_ε(1)$ trees. This result extends to any (constant) dimension and was also generalized for arbitrary doubling metrics by Bartal et al. [ICALP'19]. Although the number of trees provided by the Dumbbell Theorem is constant, this constant is not small, even for a stretch significantly larger than $1+ε$. At the other extreme, any single tree on the vertices of a regular $n$-polygon must incur a stretch of $Ω(n)$. Using known results of ultrametric embeddings, one can easily get a stretch of $\tilde{O}(\sqrt{n})$ using two trees. The question of whether a low stretch can be achieved using two trees has remained illusive, even in the Euclidean plane. In this work, we resolve this fundamental question in the affirmative by presenting a constant-stretch cover with a pair of trees, for any set of points in the Euclidean plane. Our main technical contribution is a {surprisingly simple} Steiner construction, for which we provide a {tight} stretch analysis of $\sqrt{26}$. The Steiner points can be easily pruned if one is willing to increase the stretch by a small constant. Moreover, we can bound the maximum degree of the construction by a constant. Our result thus provides a simple yet effective reduction tool -- for problems that concern approximate distances -- from the Euclidean plane to a pair of trees. To demonstrate the potential power of this tool, we present some applications [...]

  • Open Access

    Paths and Intersections: Exact Emulators for Planar Graphs

    by George Z. Li, Zihan Tan, Tianyi Zhang

    We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with $k$ terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact planar emulators of size $O(f^2k^2)$ in the setting where terminals lie on $f$ faces in the planar embedding of the input graph. Our result generalizes and interpolates between the previous results of Chang and Ophelders and Goranci, Henzinger, and Peng which is an $O(k^2)$ bound in the setting where all terminals lie on a single face (i.e., $f=1$), and the result of Krauthgamer, Nguyen, and Zondiner, which is an $O(k^4)$ bound for the general case (i.e., $f=k$). Our construction follows a recent new way of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

  • Open Access

    Approximate Light Spanners in Planar Graphs

    by Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang

    In their seminal paper, Alth\"{o}fer et al. (DCG 1993) introduced the {\em greedy spanner} and showed that, for any weighted planar graph $G$, the weight of the greedy $(1+\epsilon)$-spanner is at most $(1+\frac{2}{\epsilon}) \cdot w(MST(G))$, where $w(MST(G))$ is the weight of a minimum spanning tree $MST(G)$ of $G$. This bound is optimal in an {\em existential sense}: there exist planar graphs $G$ for which any $(1+\epsilon)$-spanner has a weight of at least $(1+\frac{2}{\epsilon}) \cdot w(MST(G))$. However, as an {\em approximation algorithm}, even for a {\em bicriteria} approximation, the weight approximation factor of the greedy spanner is essentially as large as the existential bound: There exist planar graphs $G$ for which the greedy $(1+x \epsilon)$-spanner (for any $1\leq x = O(\epsilon^{-1/2})$) has a weight of $\Omega(\frac{1}{\epsilon \cdot x^2})\cdot w(G_{OPT, \epsilon})$, where $G_{OPT, \epsilon}$ is a $(1+\epsilon)$-spanner of $G$ of minimum weight. Despite the flurry of works over the past three decades on approximation algorithms for spanners as well as on light(-weight) spanners, there is still no (possibly bicriteria) approximation algorithm for light spanners in weighted planar graphs that outperforms the existential bound. As our main contribution, we present a polynomial time algorithm for constructing, in any weighted planar graph $G$, a $(1+\epsilon\cdot 2^{O(\log^* 1/\epsilon)})$-spanner for $G$ of total weight $O(1)\cdot w(G_{OPT, \epsilon})$. To achieve this result, we develop a new technique, which we refer to as {\em iterative planar pruning}. It iteratively modifies a spanner [...]

  • Open Access

    Improved Streaming Edge Coloring

    by Shiri Chechik, Hongyi Chen, Tianyi Zhang

    Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains $n$ vertices and has maximum vertex degree $Δ$, it is known that in the W-streaming model, an $O(Δ^2)$-edge coloring can be computed deterministically with $\tilde{O}(n)$ space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an $O(Δ^{1.5})$-edge coloring can be computed by a $\tilde{O}(n)$-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to $\tilde{O}(Δ^{4/3+ε})$ using space $\tilde{O}(n)$ deterministically, for any constant $ε> 0$. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.