Computational Mathematics 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.

Synopsis:

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