More Like this

1. The worst graph layout algorithm ever

   https://doi.org/10.31219/osf.io/4hfy9  

   Di Bartolomeo, Sara; Lang, Matěj; Dunne, Cody (January 2022, Proc. alt.VIS workshop at IEEE VIS)

   Graph layout algorithms strive to improve the utility of node-link visualizations or graph drawings by optimizing for readability criteria. One such criteria that has been widely used is to count edge crossings. Prior work has focused solely on minimizing the number of edge crossings, including provably-optimal layout algorithms for layered graphs. The research community has completely ignored the other side of the coin — can we optimally maximize edge crossings? This paper answers this question in the affirmative. Our WORSTisfimal layout algorithm produces the most unreadable layered graph drawing. It does so by using linear programming to produce a provably-optimally-awful solution. We hope that this groundbreaking result opens up an entirely new field of inquiry for graph drawing researchers — optimally-worst layout algorithms. 

   more » « less
2. Stress-Plus-X (SPX) Graph Layout

   https://doi.org/10.1007/978-3-030-35802-0_23  

   Devkota, S; Ahmed, R; De Luca, F; Isaacs, K; Kobourov, S (January 2020, 27th International Symposium on Graph Drawing and Network Visualization (GD))

   Stress, edge crossings, and crossing angles play an important role in the quality and readability of graph drawings. Most standard graph drawing algorithms optimize one of these criteria which may lead to layouts that are deficient in other criteria. We introduce an optimization framework, Stress-Plus-X (SPX), that simultaneously optimizes stress together with several other criteria: edge crossings, minimum cross- ing angle, and upwardness (for directed acyclic graphs). SPX achieves results that are close to the state-of-the-art algorithms that optimize these metrics individually. SPX is flexible and extensible and can optimize a subset or all of these criteria simultaneously. Our experimental analysis shows that our joint optimization approach is successful in drawing graphs with good performance across readability criteria. 

   more » « less
3. DeepGD: A Deep Learning Framework for Graph Drawing Using GNN

   Xiaoqi Wang, Kevin Yen (September 2021, IEEE computer graphics and applications)

   Abstract—In the past decades, many graph drawing techniques have been proposed for generating aesthetically pleasing graph layouts. However, it remains a challenging task since different layout methods tend to highlight different characteristics of the graphs. Recently, studies on deep learning based graph drawing algorithm have emerged but they are often not generalizable to arbitrary graphs without re-training. In this paper, we propose a Convolutional Graph Neural Network based deep learning framework, DeepGD, which can draw arbitrary graphs once trained. It attempts to generate layouts by compromising among multiple pre-specified aesthetics considering a good graph layout usually complies with multiple aesthetics simultaneously. In order to balance the trade-off, we propose two adaptive training strategies which adjust the weight factor of each aesthetic dynamically during training. The quantitative and qualitative assessment of DeepGD demonstrates that it is capable of drawing arbitrary graphs effectively, while being flexible at accommodating different aesthetic criteria. 

   more » « less
4. Planar and poly-arc Lombardi drawings

   https://doi.org/https://doi.org/10.20382/jocg.v9i1a11  

   Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Löffler, Maarten; Nöllenburg, Martin (January 2018, Journal of computational geometry)

   In Lombardi drawings of graphs, edges are represented as circular arcs and the edges incident on vertices have perfect angular resolution. It is known that not every planar graph has a planar Lombardi drawing. We give an example of a planar 3-tree that has no planar Lombardi drawing and we show that all outerpaths do have a planar Lombardi drawing. Further, we show that there are graphs that do not even have any Lombardi drawing at all. With this in mind, we generalize the notion of Lombardi drawings to that of (smooth) k-Lombardi drawings, in which each edge may be drawn as a (differentiable) sequence of k circular arcs; we show that every graph has a smooth 2-Lombardi drawing and every planar graph has a smooth planar 3-Lombardi drawing. We further investigate related topics connecting planarity and Lombardi drawings. 

   more » « less
5. Learning a Style Space for Interactive Line Drawing Synthesis from Animated 3D Models

   Wang, Z.; Wang, T.; Dorsey, J. (October 2022, PG2022 Short Papers, Posters, and Work-in-Progress Papers)

   Umetani, N.; Wojtan, C.; Vouga, E. (Ed.)

   Most non-photorealistic rendering (NPR) methods for line drawing synthesis operate on a static shape. They are not tailored to process animated 3D models due to extensive per-frame parameter tuning needed to achieve the intended look and natural transition. This paper introduces a framework for interactive line drawing synthesis from animated 3D models based on a learned style space for drawing representation and interpolation. We refer to style as the relationship between stroke placement in a line drawing and its corresponding geometric properties. Starting from a given sequence of an animated 3D character, a user creates drawings for a set of keyframes. Our system embeds the raster drawings into a latent style space after they are disentangled from the underlying geometry. By traversing the latent space, our system enables a smooth transition between the input keyframes. The user may also edit, add, or remove the keyframes interactively, similar to a typical keyframe-based workflow. We implement our system with deep neural networks trained on synthetic line drawings produced by a combination of NPR methods. Our drawing-specific supervision and optimization-based embedding mechanism allow generalization from NPR line drawings to user-created drawings during run time. Experiments show that our approach generates high-quality line drawing animations while allowing interactive control of the drawing style across frames. 

   more » « less