Multicriteria Scalable Graph Drawing via Stochastic Gradient Descent, [Formula Omitted]

Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of other...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on visualization and computer graphics 2022-01, Vol.28 (6), p.2388
Main Authors: Reyan Ahmed, Felice De Luca, Devkota, Sabin, Kobourov, Stephen, Li, Mingwei
Format: Article
Language:English
Subjects:
Algorithms
Angular resolution
Aspect ratio
Graphical representations
Graphs
Impact analysis
Layouts
Multiple criterion
Qualitative analysis
Source code
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Multicriteria Scalable Graph Drawing via Stochastic Gradient Descent, [Formula Omitted], that can handle multiple readability criteria. [Formula Omitted] can optimize any criterion that can be described by a differentiable function. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., node resolution, angular resolution, aspect ratio). The approach is scalable and can handle large graphs. A variation of the underlying approach can also be used to optimize many desirable properties in planar graphs, while maintaining planarity. Finally, we provide quantitative and qualitative evidence of the effectiveness of [Formula Omitted]: we analyze the interactions between criteria, measure the quality of layouts generated from [Formula Omitted] as well as the runtime behavior, and analyze the impact of sample sizes. The source code is available on github and we also provide an interactive demo for small graphs.
ISSN:1077-2626
1941-0506
DOI:10.1109/TVCG.2022.3155564