Permanent URI for this collection
Browse
Recent Submissions
Publication Graph Drawing and Network Visualization. 30th International Symposium, GD 2022, Tokyo, Japan, September 13–16, 2022, Revised Selected Papers(Springer, 2023) Angelini, Patrizio; von Hanxleden, ReinhardThis book constitutes the proceedings of the 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, held in Tokyo, Japan, during September 13-16, 2022. The 25 full papers, 7 short papers, presented together with 2 invited talks, one report on graph drawing contest, and one obituary in these proceedings were carefully reviewed and selected from 70 submissions. The abstracts of 5 posters presented at the conference can be found in the back matter of the volume. The contributions were organized in topical sections as follows: properties of drawings of complete graphs; stress-based visualizations of graphs; planar and orthogonal drawings; drawings and properties of directed graphs; beyond planarity; dynamic graph visualization; linear layouts; and contact and visibility graph representations.Publication Axis-Parallel Right Angle Crossing Graphs(2023) Angelini, Patrizio; Bekos, Michael A.; Katheder, Julia; Kaufmann, Michael; Pfister, Maximilian; Ueckerdt, TorstenA RAC graph is one admitting a RAC drawing, that is, a polyline drawing in which each crossing occurs at a right angle. Originally motivated by psychological studies on readability of graph layouts, RAC graphs form one of the most prominent graph classes in beyond planarity. In this work, we study a subclass of RAC graphs, called axis-parallel RAC (or apRAC, for short), that restricts the crossings to pairs of axis-parallel edge-segments. apRAC drawings combine the readability of planar drawings with the clarity of (non-planar) orthogonal drawings. We consider these graphs both with and without bends. Our contribution is as follows: (i) We study inclusion relationships between apRAC and traditional RAC graphs. (ii) We establish bounds on the edge density of apRAC graphs. (iii) We show that every graph with maximum degree 8 is 2-bend apRAC and give a linear time drawing algorithm. Some of our results on apRAC graphs also improve the state of the art for general RAC graphs. We conclude our work with a list of open questions and a discussion of a natural generalization of the apRAC model.Publication Guest Editors’ Foreword(2023) Angelini, Patrizio; von Hanxleden, ReinhardPublication Morphing Triangle Contact Representations of Triangulations(Springer Nature, 2023) Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano; Roselli, VincenzoA morph is a continuous transformation between two representations of a graph. We consider the problem of morphing between contact representations of a plane graph. In an F-contact representation of a plane graph G, vertices are realized by internally disjoint elements from a family F of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in G. In a morph between two F-contact representations we insist that at each time step (continuously throughout the morph) we have an Fcontact representation. We focus on the case when F is the family of triangles in R2 that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Moreover, they naturally correspond to 3-orientations. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We characterize the pairs of RT-representations admitting a morph between each other via the respective 3-orientations. Our characterization leads to a polynomial-time algorithm to decide whether there is a morph between two RTrepresentations of an n-vertex plane triangulation, and, if so, computes a morph with O(n2) steps. Each of these steps is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. Our characterization also implies that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the “top-most” triangle in both representations corresponds to the same vertex.Publication Splitting Vertices in 2-Layer Graph Drawings(IEEE, 2023) Ahmed, Reyan; Angelini, Patrizio; Bekos, Michael A.; Di Battista, Giuseppe; Kaufmann, Michael; Kindermann, Philipp; Kobourov, Stephen G.; Nöllenburg, Martin; Symvonis, Antonios; Villedieu, Anaïs; Wallinger, MarkusBipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two sets of entities (vertices) are placed on two parallel lines (layers), and their relationships (edges) are represented by segments connecting vertices. Methods for constructing 2-layer drawings often try to minimize the number of edge crossings. We use vertex splitting to reduce the number of crossings, by replacing selected vertices on one layer by two (or more) copies and suitably distributing their incident edges among these copies. We study several optimization problems related to vertex splitting, either minimizing the number of crossings or removing all crossings with fewest splits. While we prove that some variants are NPNP-complete, we obtain polynomial-time algorithms for others. We run our algorithms on a benchmark set of bipartite graphs representing the relationships between human anatomical structures and cell types.Publication Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario(Springer Nature, 2023) Angelini, Patrizio; Bekos, Michael A.; Förster, Henry; Gronemann, MartinBitonic st-orderings for st-planar graphs were introduced as a method to cope with several graph drawing problems. Notably, they have been used to obtain the best-known upper bound on the number of bends for upward planar polyline drawings with at most one bend per edge in polynomial area. For an st-planar graph that does not admit a bitonic st-ordering, one may split certain edges such that for the resulting graph such an ordering exists. Since each split is interpreted as a bend, one is usually interested in splitting as few edges as possible.While this optimization problem admits a linear-time algorithm in the fixed embedding setting, it remains open in the variable embedding setting. We close this gap in the literature by providing a linear-time algorithm that optimizes over all embeddings of the input st-planar graph. The best-known lower bound on the number of required splits of an st-planar graph with n vertices is n − 3. However, it is possible to compute a bitonic st-ordering without any split for the stplanar graph obtained by reversing the orientation of all edges. In terms of upward planar polyline drawings in polynomial area, the former translates into n − 3 bends, while the latter into no bends. We show that this idea cannot always be exploited by describing an st-planar graph that needs at least n − 5 splits in both orientations. We provide analogous bounds for graphs with small degree. Finally, we further investigate the relationship between splits in bitonic st-orderings and bends in upward planar polyline drawings with polynomial area, by providing bounds on the number of bends in such drawings.Publication 2-Layer k-Planar Graphs Density, Crossing Lemma, Relationships And Pathwidth(2024) Angelini, Patrizio; Da Lozzo, Giordano; Förster, Henry; Schneck, ThomasThe 2-layer drawing model is a well-established paradigm to visualize bipartite graphs where vertices of the two parts lie on two horizontal lines and edges lie between these lines. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of k-planar graphs has been considered only for k = 1 in this context. We provide several contributions that address this gap in the literature. First, we show tight density bounds for the classes of 2-layer k-planar graphs with k ∈ {2, 3, 4, 5}. Based on these results, we provide a Crossing Lemma for 2-layer k-planar graphs, which then implies a general density bound for 2-layer k-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between k-planarity and h-quasiplanarity in the 2-layer model and show that 2-layer k-planar graphs have pathwidth at most k + 1 while there are also 2-layer k-planar graphs with pathwidth at least (k + 3)/2.Publication Recognizing Map Graphs of Bounded Treewidth(Springer Nature, 2024) Angelini, Patrizio; Bekos, Michael A.; Da Lozzo, Giordano; Gronemann, Martin; Montecchiani, Fabrizio; Tappini, AlessandraA map is a partition of the sphere into interior-disjoint regions homeomorphic to closed disks. Some regions are labeled as nations, while the remaining ones are labeled as holes. A map in which at most k nations touch at the same point is a k-map, while it is hole-free if it contains no holes. A graph is a map graph if there is a bijection between its vertices and the nations of a map, such that two nations touch if and only the corresponding vertices are connected by an edge. We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph. It reports a certificate in the form of a so-called witness, if the input is a yes-instance. Our algorithmic framework is general enough to test, for any k, if the input graph admits a k-map or a hole-free k-map.