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
Density Theorems for Intersection Graphs of t-Monotone Curves
No full textA curve γ in the plane is t-monotone if its interior has at most vertical tangent points. A family of t-monotone curves F is simple if any two members intersect at most once. It is shown that if F is a simple family of n t-monotone curves with at least intersecting pairs (disjoint pairs), then there exists two subfamilies of size δn each, such that every curve in intersects (is disjoint to) every curve in , where δ depends only on ε. We apply these results to find pairwise disjoint edges in simple topological graphs
Drawing Metro Maps Using Bézier Curves
No full textThe automatic layout of metro maps has been investigated quite intensely over the last few years. Previous work has focused on the octilinear drawing style where edges are drawn horizontally, vertically, or diagonally at 45°. Inspired by manually created curvy metro maps, we advocate the use of the curvilinear drawing style; we draw edges as Bézier curves. Since we forbid metro lines to bend (even in stations), the user of such a map can trace the metro lines easily. In order to create such drawings, we use the force-directed framework. Our method is the first that directly represents and operates on edges as curves
Characterizing Planarity by the Splittable Deque
No full textA graph layout describes the processing of a graph G by a data structure , and the graph is called a -graph. The vertices of G are totally ordered in a linear layout and the edges are stored and organized in . At each vertex, all edges to predecessors in the linear layout are removed and all edges to successors are inserted. There are intriguing relationships between well-known data structures and classes of planar graphs: The stack graphs are the outerplanar graphs [4], the queue graphs are the arched leveled-planar graphs [12], the 2-stack graphs are the subgraphs of planar graphs with a Hamilton cycle [4], and the deque graphs are the subgraphs of planar graphs with a Hamilton path [2]. All of these are proper subclasses of the planar graphs, even for maximal planar graphs.
We introduce splittable deques as a data structure to capture planarity. A splittable deque is a deque which can be split into sub-deques. The splittable deque provides a new insight into planarity testing by a game on switching trains. Here, we use it for a linear-time planarity test of a given rotation system
Morphing Planar Graph Drawings Efficiently
No full textA morph between two straight-line planar drawings of the same graph is a continuous transformation from the first to the second drawing such that planarity is preserved at all times. Each step of the morph moves each vertex at constant speed along a straight line. Although the existence of a morph between any two drawings was established several decades ago, only recently it has been proved that a polynomial number of steps suffices to morph any two planar straight-line drawings. Namely, at SODA 2013, Alamdari et al. [1] proved that any two planar straight-line drawings of a planar graph can be morphed in O(n 4) steps, while O(n 2) steps suffice if we restrict to maximal planar graphs.
In this paper, we improve upon such results, by showing an algorithm to morph any two planar straight-line drawings of a planar graph in O(n 2) steps; further, we show that a morph with O(n) steps exists between any two planar straight-line drawings of a series-parallel graph
Streamed Graph Drawing and the File Maintenance Problem
No full textIn streamed graph drawing, a planar graph, G, is given incrementally as a data stream and a straight-line drawing of G must be updated after each new edge is released. To preserve the mental map, changes to the drawing should be minimized after each update, and Binucci et al. show that exponential area is necessary for a number of streamed graph drawings for trees if edges are not allowed to move at all. We show that a number of streamed graph drawings can, in fact, be done with polynomial area, including planar streamed graph drawings of trees, tree-maps, and outerplanar graphs, if we allow for a small number of coordinate movements after each update. Our algorithms involve an interesting connection to a classic algorithmic problem—the file maintenance problem—and we also give new algorithms for this problem in a framework where bulk memory moves are allowe
Colored Spanning Graphs for Set Visualization
No full textWe study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected.
We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem is NP-hard. Hence we give an (12ρ+1) -approximation, where ρ is the Steiner ratio. We also present efficient exact solutions if the points are located on a line or a circle. Finally we consider extensions to more than two sets
Strict Confluent Drawing
No full textWe define strict confluent drawing, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be unique. We prove that it is NP-complete to determine whether a given graph has a strict confluent drawing but polynomial to determine whether it has an outerplanar strict confluent drawing with a fixed vertex ordering (a drawing within a disk, with the vertices placed in a given order on the boundary)
Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings
No full textWe present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based representation vertices and edges correspond to axis-parallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problem-specific constraints. We describe a general d-dimensional model for grid representation problems. This model can be used to solve a variety of NP-hard graph problems, including pathwidth, bandwidth, optimum \textit{st}-orientation, area-minimal (bar-\textit{k}) visibility representation, boxicity-k graphs and others. We implemented SAT-models for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NP-hard problems within few minutes on small to medium-size Rome graphs
Untangling Two Systems of Noncrossing Curves
No full textWe consider two systems (α 1,…,α m ) and (β 1,…,β n ) of curves drawn on a compact two-dimensional surface with boundary. Each α i and each β j is either an arc meeting the boundary of at its two endpoints, or a closed curve. The α i are pairwise disjoint except for possibly sharing endpoints, and similarly for the β j . We want to “untangle” the β j from the α i by a self-homeomorphism of ; more precisely, we seek an homeomorphism φ→ fixing the boundary of pointwise such that the total number of crossings of the α i with the ϕ(β j ) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds.
We prove that if is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g
The Approximate Rectangle of Influence Drawability Problem
No full textWe prove that all planar graphs have an open/closed -rectangle of influence drawing for and , while there are planar graphs which do not admit an open/closed -rectangle of influence drawing and planar graphs which do not admit a -rectangle of influence drawing. We then show that all outerplanar graphs have an open/closed -rectangle of influence drawing for any ε_2 ≥ 0. We also prove that if an open/closed -rectangle of influence drawing of an outerplanar graph can be computed in polynomial area. For values of such that , we describe a drawing algorithm that computes -rectangle of influence drawings of binary trees in area , where is a logarithmic function that tends to infinity as tends to zero, and n is the number of vertices of the input tree