<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt;">
<div class="PlainText">This is an announcement of Zihan Tan's Dissertation Defense.<br>
===============================================<br>
Candidate: Zihan Tan<br>
<br>
Date: Monday, April 25, 2022<br>
<br>
Time: 2 pm CST<br>
<br>
Remote Location: Zoom Link: <a href="https://uchicago.zoom.us/j/97442905405?pwd=L0lrcUdKT3N2NkJLMzd3RmtLQStmZz09">
https://uchicago.zoom.us/j/97442905405?pwd=L0lrcUdKT3N2NkJLMzd3RmtLQStmZz09</a> Meeting ID：974 4290 5405 Passcode：260447<br>
<br>
<br>
Title: From Structural Graph Theory To Graph Algorithms, And Back<br>
<br>
Abstract: In this thesis we study two algorithmic problems on graphs: Graph Crossing Number and the Packing of Low-Diameter Spanning Trees.<br>
<br>
In the first part of the thesis, we consider the Graph Crossing Number problem, in which we are given a graph and are asked to find a drawing of it in the plane that minimizes the number of crossings. For bounded-degree graphs, almost all previous algorithms
followed the same framework, and the best of them achieved an Õ(⎷n)-approximation, which was also proved to be optimal in this framework. We propose a new framework that overcomes this barrier. This allows us to reduce the problem to another related problem
called the Crossing Number with Rotation System problem, and eventually obtain an n^o(1)-approximation for the Crossing Number problem on low-degree graphs.<br>
<br>
In the second part of this thesis, we study the problem of packing low-diameter spanning trees. The celebrated tree-packing theorem due to Tutte and Nash-Williams states that every 2k-edge-connected graph contains k edge-disjoint spanning trees. We use the
techniques of randomized algorithms to show that every 2k-edge-connected graph with diameter D contains k spanning trees with diameter k^O(D) each, that cause edge-congestion 2. We then show that the same techniques can be applied to improve the Karger's edge-sampling
theorem. Finally, we use these graph-theoretic results to improve the round complexities of various distributed graph algorithms.<br>
<br>
<br>
<br>
Advisors: Laci Babai and Julia Chuzhoy<br>
<br>
Committee Members: Julia Chuzhoy, Laci Babai, and Lorenzo Orecchia<br>
<br>
</div>
</span></font></div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt;">
<div class="PlainText"><br>
<br>
</div>
</span></font></div>
</body>
</html>