John Urschel, MIT
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.
John Urschel is an applied mathematician in his fifth year of a PhD program in math at MIT. His research focuses on numerical analysis, graph theory, and data science/machine learning. Urschel is primarily interested in theoretical results and provable guarantees for practical algorithms/problems, which often lead to new and improved algorithms. He is advised by Michel Goemans and expects to graduate in Spring 2021. More information about his publications and research may be found at math.mit.edu/~urschel.