Yuchong Pan 潘宇冲

2024

1. SIDMA

   

   Planarity via Spanning Tree Number: A Linear-Algebraic Criterion

   Alan Bu, and Yuchong Pan

   SIAM J. Discrete Math., 2024

   Abs Bib PDF Poster Slides

   We introduce a novel linear-algebraic planarity criterion based on the number of spanning trees. We call a matrix an incidence submatrix if each row has at most one 1, at most one -1, and all other entries zero. Given a connected graph G with m edges, we consider the maximum determinant \mathsf{maxdet}(G) of an m \times m matrix [M|N], where M is the incidence matrix of G with one column removed, over all incidence submatrices N of appropriate size, and define its excess to be the number of spanning trees in G minus \mathsf{maxdet}(G). Given a disconnected graph, we define its excess to be the sum of the excesses of its connected components. We show that the excess of a graph is 0 if it is planar, and at least 18 otherwise. This provides a “certificate of planarity” of a planar graph that can be verified by computing the determinant of a sparse matrix and counting spanning trees. Furthermore, we derive an upper bound on the maximum determinant of an m \times m matrix [M|N], where M and N are incidence submatrices. Motivated by this bound and numerical evidence, we conjecture that this maximum determinant is equal to the maximum number of spanning trees in a planar graph with m edges. We present partial progress towards this conjecture. In particular, we prove that the \mathsf{maxdet}(⋅) value of any subdivision of K_{3, 3} or K_5 is at most that of the best planar graph with the same number of edges.

   @article{bu2024planarity,
     title = {Planarity via Spanning Tree Number: A Linear-Algebraic Criterion},
     author = {Bu, Alan and Pan, Yuchong},
     journal = {SIAM J. Discrete Math.},
     year = {2024},
     publisher = {Society for Industrial and Applied Mathematics},
   }

2021

1. 

   Optimization Problems on Network Flows with Degree Constraints

   Yuchong Pan

   2021

   Abs Bib PDF

   In a vertex-capacitated directed graph with sources and sinks, we would like to concurrently route demands from the sources to the sinks. This model has many applications in the real world. However, conditions in the reality usually incur new side constraints to this general model. For instance, the next-hop routing in Internet protocol (IP) networks requires each router to have one single next destination, called the next hop, for each incoming packet destined to an IP address. A flow with this property is said to be confluent. If this constraint is relaxed to allow d next destinations at each vertex, then such a flow is said to be d-furcated. In general, side constraints concerning bounded out-degree of each vertex give rise to network flows with degree constraints. Such constraints contribute to simplicity of resulting network flow models. Given a network flow model, several optimization problems can be asked. For instance, how the demands can be routed so that the flow does not exceed the capacity at each vertex too much? Another natural question is to find a subset of the demands with the maximum amount which can be routed subject to the vertex capacities. In this thesis, we survey algorithms that find approximate solutions close to optimum values within theoretically guaranteed factors.

   @masterthesis{pan2021optimization,
     title = {Optimization Problems on Network Flows with Degree Constraints},
     author = {Pan, Yuchong},
     year = {2021},
     type = {Undergraduate Honours Thesis},
     school = {University of British Columbia},
   }