Numerical Analysis and Scientific Computing Seminar
Some Results on Force-Directed Drawings of Graphs
Speaker: John Urschel, Massachusetts Institute of Technology
Location: Warren Weaver Hall (online)
Date: Oct. 16, 2020, 10 a.m.
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.See https://cs.nyu.edu/dynamic/news/seminars/1/ for how to join the seminar via Zoom