Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
Graph Drawing E-print ArchiveNot a member yet
1225 research outputs found
Sort by
Computing NodeTrix Representations of Clustered Graphs
No full textNodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and inter-cluster edges as curves connecting the matrix boundaries. We study the complexity of constructing NodeTrix representations focusing on planarity testing problems, and we show several NPNP -completeness results and some polynomial-time algorithms
Non-aligned Drawings of Planar Graphs
No full textA non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have a non-aligned planar straight-line drawing in the n×n -grid. They also showed that such a drawing exists if up to n−3 edges may have a bend.
In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an n×n -grid with at most (2n−5)/3 bends, and we study what grid-size can be achieved if we insist on having straight-line drawings
Stack and Queue Layouts via Layered Separators
No full textIt is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not closed under taking minors. For fixed g and k, we show that every n-vertex graph that can be embedded on a surface of genus g with at most k crossings per edge has stack-number O(logn); this includes k-planar graphs. The previously best known bound for the stack-number of these families was O(√n), except in the case of 1-planar graphs. Analogous results are proved for map graphs that can be embedded on a surface of fixed genus. None of these families is closed under taking minors. The main ingredient in the proof of these results is a construction proving that n-vertex graphs that admit constant layered separators have O(logn) stack-number
Graph Drawing Contest Report
No full textThis report describes the 23rd Annual Graph Drawing Contest, held in conjunction with the 24th International Symposium on Graph Drawing (GD’16) in Athens, Greece. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology
Multi-colored Spanning Graphs
No full textWe study a problem proposed by Hurtado et al. [10] motivated by sparse set visualization. Given n points in the plane, each labeled with one or more primary colors, a colored spanning graph (CSG) is a graph such that for each primary color, the vertices of that color induce a connected subgraph. The Min-CSG problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NP-hard for k primary colors when k≥3 and provide a (2−1/(3+2ϱ))-approximation algorithm for k=3 that runs in polynomial time, where ϱ is the Steiner ratio. Further, we give a O(n) time algorithm in the special case that the input points are collinear and k is constant
Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
No full textThomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335–341, 1988].
In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Re-embedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration
On the Density of Non-simple 3-Planar Graphs
No full textA k-planar graph is a graph that can be drawn in the plane such that every edge is crossed at most k times. For k≤4, Pach and Tóth [20] proved a bound of (k+3)(n−2) on the total number of edges of a k-planar graph, which is tight for k=1,2. For k=3, the bound of 6n−12 has been improved to 11/2n−11 in [19] and has been shown to be optimal up to an additive constant for simple graphs. In this paper, we prove that the bound of 11/2n−11 edges also holds for non-simple 3-planar graphs that admit drawings in which non-homotopic parallel edges and self-loops are allowed. Based on this result, a characterization of optimal 3-planar graphs (that is, 3-planar graphs with n vertices and exactly 11/2n−11 edges) might be possible, as to the best of our knowledge the densest known simple 3-planar is not known to be optimal
Crossing Minimization in Storyline Visualization
No full textA storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented at improving aesthetics and legibility of a representation of this type, a small number of line crossings is the hardest to achieve. We model the crossing minimization in the storyline visualization problem as a multi-layer crossing minimization problem with tree constraints. Our algorithm can compute a layout with the minimum number of crossings of the chronological lines. Computational results demonstrate that it can solve instances with more than 100 interactions and with more than 100 chronological lines to optimality
