静5青年讲座 | Paths and Intersections

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    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    bound in the setting where all terminals lie on a single face (i.e.,   ), and the result of Krauthgamer, Nguyen, and Zondiner, which is an    bound for the general case (i.e.,   ). 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. This talk is based on joint work with George Li and Tianyi Zhang.

Zihan Tan is an assistant professor at Department of Computer Science and Engineering of University of Minnesota Twin Cities. Before joining UMN, he spent a year as an assistant professor at Computer Science Department at Rutgers University. Prior to that, he obtained his PhD from University of Chicago and spent two years as a postdoc at DIMACS (Center of Discrete Math and Computer Science) at Rutgers University. He is broadly interested in theoretical computer science. Currently his research focuses on graph theory and graph algorithms.