News & Events

Widely Applied Mathematics Seminars

Some Results on Force-Directed Drawings of Graphs

John Urschel, MIT

Thursday, Oct 29, 2020
3:00 pm to 4:00 pm | Zoom

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.

Speaker Bio

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.

Contact
Host:

Michael Brenner

Contact:

Nick Grall

You're not going yet!

This event requires registration.