Math/CS Colloquium: John Urschel, Massachusetts Institute of Technology

Some Results on Force-Directed Drawings of Graphs (recording of talk found here)

Abstract: Given a discrete graph, the problem of drawing it in low-dimensional Euclidean space is an important one, for the sake of visualization. In this talk, we review different force-directed techniques for drawing a graph, such as Tutte's spring embedding theorem for three-connected planar graphs, modern techniques such as stress-majorization/Kamada-Kawai, and the more recent use of force-directed drawings in popular data visualization algorithms such UMAP. We connect the spring embedding problem to discrete trace theorems, investigate algorithms and algorithmic lower bounds for stress-majorization, and talk about how these techniques can be applied to more complex objectives.

Bio: I am an applied mathematician. My research is focused on numerical analysis, graph theory, and data science/machine learning. I am primarily interested in theoretical results and provable guarantees for practical algorithms/problems, which often lead to new and improved algorithms.

I am currently a fifth-year PhD student at MIT math, and have the pleasure of being advised by Michel Goemans. I expect to graduate in Spring 2021.

Here are a few selected publications:
1. Uniform Error Estimates for the Lanczos Method, Preprint (2020) [PDF]
2. Regarding Two Conjectures on Clique and Biclique Partitions, Preprint (2020) [PDF]
3. On the Characterization and Uniqueness of Centroidal Voronoi Tessellations, SINUM (2017) [PDF]
4. Learning Determinantal Point Processes with Moments and Cycles, ICML (2017) [PDF]
5. Spectral Bisection of Graphs and Connectedness, Lin Alg & App (2014) [PDF]

Below, you can find a detailed description of my research, a full list of my publications, and my current and past teaching. Here is a (most likely outdated) CV. My research and teaching statements are available upon request.