More Like this

1. 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
2. Drawing Shortest Paths in Geodetic Graphs

   Cornelsen, S; Pfister, M; Foerster, H; Gronemann, M; Hoffmann, M; Kobourov, S; Schneck, T (October 2020, 28th International Symposium on Graph Drawing and Network Visualization (GD))

   Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing. 

   more » « less
3. Universal Geometric Graphs

   https://doi.org/10.1007/978-3-030-60440-0_14  

   Frati, Fabrizio; Hoffmann, Michael; Toth, Csaba D. (October 2020, Graph-Theoretic Concepts in Computer Science (WG 2020))

   null (Ed.)

   We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars. 

   more » « less
4. Geometric Graphs with Unbounded Flip-Width

   Eppstein, D; McCarty, R (August 2023, Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG))

   Pankratov, D (Ed.)

   We consider the flip-width of geometric graphs, a notion of graph width recently introduced by Toruńczyk. We prove that many different types of geometric graphs have unbounded flip-width. These include interval graphs, permutation graphs, circle graphs, intersection graphs of axis-aligned line segments or axis-aligned unit squares, unit distance graphs, unit disk graphs, visibility graphs of simple polygons, β-skeletons, 4-polytopes, rectangle of influence graphs, and 3d Delaunay triangulations. 

   more » « less
5. Graph drawing via gradient descent,

   Ahmed, R; De Luca, F; Devkota, S; Kobourov, S; Li, M (October 2020, 28th International Symposium on Graph Drawing and Network Visualization (GD))

   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, Graph Drawing via Gradient Descent, (GD)^2, that can handle multiple readability criteria. (GD)^2 can optimize any criterion that can be described by a smooth function. If the criterion cannot be captured by a smooth function, a non-smooth function for the criterion is combined with another smooth function, or auto-differentiation tools are used for the optimization. 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., vertex resolution, angular resolution, aspect ratio). We provide quantitative and qualitative evidence of the effectiveness of (GD)^2 with experimental data and a functional prototype: http://hdc.cs.arizona.edu/~mwli/graph-drawing/ 

   more » « less