More Like this

1. Simple Topological Drawings of k-Planar Graphs.

   https://doi.org/10.1007/978-3-030-68766-3_31  

   Hoffmann, Michael; Liu, Chih-Hung; Reddy, Meghana M.; Toth, Csaba D. (February 2021, Graph Drawing and Network Visualization)

   null (Ed.)

   Every finite graph admits a simple (topological) drawing, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for k≤3 , every k-planar graph admits a k-plane simple drawing. But for k≥4 , there exist k-planar graphs that do not admit a k-plane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every k-planar graph admits an f(k)-plane simple drawing, for all Open image in new window. Note that the function f depends on k only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every 4-planar graph admits an 8-plane simple drawing. 

   more » « less
2. Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature

   https://doi.org/10.4230/LIPIcs.GD.2024.39  

   Eppstein, David; Goodrich, Michael T; Illickan, Abraham M (October 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Felsner, Stefan; Klein, Karsten (Ed.)

   We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC drawing using a single cubic Bézier curve per edge, and this drawing can be computed in O(n) time given a combinatorial 1-planar drawing. We also show that any n-vertex planar graph G can be drawn in O(n) time with a single cubic Bézier curve per edge, in an O(n)× O(n) bounding box, such that the edges have Θ(1/degree(v)) angular resolution, for each v ∈ G, and O(√n) curvature. 

   more » « less
3. 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
4. The Widths of Strict Outerconfluent Graphs

   https://doi.org/10.46298/dmtcs.12862  

   Eppstein, David (December 2024, Discrete Mathematics & Theoretical Computer Science)

   Strict outerconfluent drawing is a style of graph drawing in which vertices are drawn on the boundary of a disk, adjacencies are indicated by the existence of smooth curves through a system of tracks within the disk, and no two adjacent vertices are connected by more than one of these smooth tracks. We investigate graph width parameters on the graphs that have drawings in this style. We prove that the clique-width of these graphs is unbounded, but their twin-width is bounded. Comment: Final version for DMTCS; 17 pages, 2 figures 

   more » « less
5. The Multi-Dimensional Landscape of Graph Drawing Metrics

   Mooney, Gavin; Purchase, Helen; Wybrow, Michael; Kobourov, Stephen (April 2024, 17th IEEE Pacific Visualization Symposium (PACIFICVIS))

   Any graph drawing can be characterised by a range of computational aesthetic metrics. For example, a given drawing might be described as having eight crossings, a mean angular resolution of 0.34, and an edge orthogonality value of 0.72. However, without knowing the distribution of these metrics it is hard to compare the quality of drawings of different graphs, nor know whether a given drawing is typical or an outlier within the space of all possible drawings. This paper explores the range and distribution of ten normalised graph drawing layout metrics, based on graphs created by six graph generation algorithms and drawings created by six popular layout algorithms. We include the “Rome" and “North" graph repositories in our analysis. Our exploration of the multi-dimensional aesthetics space allows for comparisons between the graph drawing algorithms, highlighting those that cover larger or smaller volumes of the aesthetics space. We calculate the correlation coefficients between the metrics, indicating those that may conflict with each other (negatively correlated), and those that may be redundant (positively correlated). Our results will be useful as the basis for simulated annealing or gradient descent layout algorithms, for identifying the best layout algorithms for producing a specified combination and range of aesthetics, and for informing experimental controls in human empirical studies. 

   more » « less