Seminar • Algorithms and Complexity • From Geometry to Graphs: A Geometric Perspective on Topological and Geometric Graphs

Please note: This seminar will take place in DC 1304.

David Zheng, PhD candidate
University of Illinois Urbana-Champaign

Geometric intersection graphs are useful for modeling relationships in wireless networks and other spatial systems. Similarly, topological graphs, including planar graphs, have applications in geographical information systems, wireless networks, and VLSI design. While the complexity of fundamental problems such as computing connected components or graph diameter is well understood for general graphs, surprising gaps remained for these specialized graph classes. In this talk, I will share recent results that demonstrate how geometric intuition can lead to both efficient solutions to these problems and deeper structural insight into these graphs.

Bio: David Zheng is a PhD candidate at the University of Illinois Urbana-Champaign (UIUC) where he is advised by Timothy Chan. He holds a Master’s and Bachelor’s degree from the University of British Columbia (UBC).

His research in theoretical computer science focuses on computational geometry and graph algorithms. He has also received recognition for implementing algorithms for geometric optimization problems, earning top-three finishes in the CG:SHOP challenge held at SoCG 2020, 2021, and 2022.