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 Storyline Visualizations with Few Block Crossings
No full textStoryline visualizations show the structure of a story, by depicting the interactions of the characters over time. Each character is represented by an x-monotone curve from left to right, and a meeting is represented by having the curves of the participating characters run close together for some time. There have been various approaches to drawing storyline visualizations in an automated way. In order to keep the visual complexity low, rather than minimizing pairwise crossings of curves, we count block crossings, that is, pairs of intersecting bundles of lines.
Partly inspired by the ILP-based approach of Gronemann et al. [GD 2016] for minimizing the number of pairwise crossings, we model the problem as a satisfiability problem (since the straightforward ILP formulation becomes more complicated and harder to solve). Having restricted ourselves to a decision problem, we can apply powerful SAT solvers to find optimal drawings in reasonable time. We compare this SAT-based approach with two exact algorithms for block crossing minimization, using both the benchmark instances of Gronemann et al. and random instances. We show that the SAT approach is suitable for real-world instances and identify cases where the other algorithms are preferable
Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity
No full textWe introduce and study the problem Ordered Level Planarity which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge is realized as a y-monotone curve. This can be interpreted as a variant of Level Planarity in which the vertices on each level appear in a prescribed total order. We establish a complexity dichotomy with respect to both the maximum degree and the level-width, that is, the maximum number of vertices that share a level. Our study of Ordered Level Planarity is motivated by connections to several other graph drawing problems.
Geodesic Planarity asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge e is realized as a polygonal path p composed of line segments with two adjacent directions from a given set S of directions symmetric with respect to the origin. Our results on Ordered Level Planarity imply
-hardness for any S with |S|≥4 even if the given graph is a matching. Katz, Krug, Rutter and Wolff claimed that for matchings Manhattan Geodesic Planarity, the case where S contains precisely the horizontal and vertical directions, can be solved in polynomial time [GD 2009]. Our results imply that this is incorrect unless =P
. Our reduction extends to settle the complexity of the Bi-Monotonicity problem, which was proposed by Fulek, Pelsmajer, Schaefer and Štefankovič.
Ordered Level Planarity turns out to be a special case of T-Level Planarity, Clustered Level Planarity and Constrained Level Planarity. Thus, our results strengthen previous hardness results. In particular, our reduction to Clustered Level Planarity generates instances with only two non-trivial clusters. This answers a question posed by Angelini, Da Lozzo, Di Battista, Frati and Roselli
An Interactive Tool to Explore and Improve the Ply Number of Drawings
No full textGiven a straight-line drawing Γ of a graph G=(V,E), for every vertex v the ply disk Dv is defined as a disk centered at v where the radius of the disk is half the length of the longest edge incident to v. The ply number of a given drawing is defined as the maximum number of overlapping disks at some point in IR2. Here we present a tool to explore and evaluate the ply number for graphs with instant visual feedback for the user. We evaluate our methods in comparison to an existing ply computation by De Luca et al. [WALCOM’17]. We are able to reduce the computation time from seconds to milliseconds for given drawings and thereby contribute to further research on the ply topic by providing an efficient tool to examine graphs extensively by user interaction as well as some automatic features to reduce the ply number
Thrackles: An Improved Upper Bound.
No full textA thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3/2(n−1), and that this bound is best possible for infinitely many values of n
The Effect of Planarization on Width.
No full textWe study the effects of planarization (the construction of a planar diagram D from a non-planar graph G by replacing each crossing by a new vertex) on graph width parameters. We show that for treewidth, pathwidth, branchwidth, clique-width, and tree-depth there exists a family of n-vertex graphs with bounded parameter value, all of whose planarizations have parameter value Ω(n). However, for bandwidth, cutwidth, and carving width, every graph with bounded parameter value has a planarization of linear size whose parameter value remains bounded. The same is true for the treewidth, pathwidth, and branchwidth of graphs of bounded degree
Reconstructing Generalized Staircase Polygons with Uniform Step Length
No full textVisibility graph reconstruction, which asks us to construct a polygon that has a given visibility graph, is a fundamental problem with unknown complexity (although visibility graph recognition is known to be in PSPACE). We show that two classes of uniform step length polygons can be reconstructed efficiently by finding and removing rectangles formed between consecutive convex boundary vertices called tabs. In particular, we give an O(n2m)-time reconstruction algorithm for orthogonally convex polygons, where n and m are the number of vertices and edges in the visibility graph, respectively. We further show that reconstructing a monotone chain of staircases (a histogram) is fixed-parameter tractable, when parameterized on the number of tabs, and polynomially solvable in time O(n2m) under reasonable alignment restrictions