Oliver Club

John UrschelMIT
Some results on force-directed drawings of graphs

Thursday, October 15, 2020 - 4:00pm
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.