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
Edge-Weighted Contact Representations of Planar Graphs
No full textWe study contact representations of edge-weighted planar graphs, where vertices are rectangles or rectilinear polygons and edges are polygon contacts whose lengths represent the edge weights. We show that for any given edge-weighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no separating triangles we can construct in linear time an edge-proportional rectangular dual if one exists and report failure otherwise. For a given combinatorial structure of the contact representation and edge weights interpreted as lower bounds on the contact lengths, a corresponding contact representation that minimizes the size of the enclosing rectangle can be found in linear time.If the combinatorial structure is not fixed, we prove NP-hardness of deciding whether a contact representation with bounded contact lengths exists.
Finally, we give a complete characterization of the rectilinear polygon complexity required for representing biconnected internally triangulated graphs: For outerplanar graphs complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the complexity is unbounded
Column-Based Graph Layouts
No full textWe consider orthogonal upward drawings of directed acyclic graphs (DAGs) with nodes of uniform width but node-specific height. One way to draw such graphs is to use a layering technique as provided by the Sugiyama framework [10]. However, to avoid drawbacks of the Sugiyama framework we use the layer-free upward crossing minimization algorithm suggested by Chimani et al. and integrate it into the topology-shape-metric (TSM) framework introduced by Tamassia [11]. This in combination with an algorithm by Biedl and Kant [2] lets us generate column-based layouts, i.e., layouts where the plane is divided into uniform-width columns and every node is assigned to a column.
We show that our column-based approach allows to generate visually appealing, compact layouts with few edge crossing and at most four bends per edge. Furthermore, the resulting layouts exhibit a high degree of symmetry and implicitly support edge bundling. We justify our approach by an experimental evaluation based on real-world examples
Kinetic and Stationary Point-Set Embeddability for Plane Graphs
No full textWe investigate a kinetic version of point-set embeddability. Given a plane graph , and a set P of n moving points where the trajectory of each point is an algebraic function of constant maximum degree s, we maintain a point-set embedding of G on P with at most three bends per edge during the motion. This requires reassigning the mapping of vertices to points from time to time. Our kinetic algorithm uses linear size, O(nlogn) preprocessing time, and processes events, each in time. Here, is an extremely slow-growing function and is the maximum length of Davenport-Schinzel sequences of order s on n symbols
A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes
No full textWe study the problem of how to obtain an integer realization of a 3d polytope when an integer realization of its dual polytope is given. We focus on grid embeddings with small coordinates and develop novel techniques based on Colin de Verdière matrices and the Maxwell–Cremona lifting method.
As our main result we show that every truncated 3d polytope with n vertices can be realized on a grid of size polynomial in n. Moreover, for a class C of simplicial 3d polytopes with bounded vertex degree, at least one vertex of degree 3, and polynomial size grid embedding, the dual polytopes of C can be realized on a polynomial size grid as well
Block Additivity of ℤ2-Embeddings
No full textWe study embeddings of graphs in surfaces up to ℤ2-homology. We introduce a notion of genus mod 2 and show that some basic results, most noteworthy block additivity, hold for ℤ2-genus. This has consequences for (potential) Hanani-Tutte theorems on arbitrary surfaces
Exploring Complex Drawings via Edge Stratification
No full textWe propose an approach that allows a user to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; layers can be explored and combined by the user to gradually acquire details. We present stratification heuristics, a user study, and an experimental analysis that evaluates how our stratification heuristics behave on the drawings computed by a variety of popular force-directed algorithms
Slanted Orthogonal Drawings
No full textWe introduce a new model that we call slanted orthogonal graph drawing. While in traditional orthogonal drawings each edge is made of axis-aligned line-segments, in slanted orthogonal drawings intermediate diagonal segments on the edges are also permitted, which allows for: (a) smoothening the bends of the produced drawing (as they are replaced by pairs of “half-bends”), and, (b) emphasizing the crossings of the drawing (as they always appear at the intersection of two diagonal segments). We present an approach to compute bend-optimal slanted orthogonal representations, an efficient heuristic to compute close-to-optimal drawings in terms of the total number of bends using quadratic area, and a corresponding LP formulation, when insisting on bend optimality. On the negative side, we show that bend-optimal slanted orthogonal drawings may require exponential area
Browser-Based Graph Visualization of Dynamic Data with VisGraph
No full textVisGraph is an open-source JavaScript library for the realtime graph visualization of dynamic data in a browser. Its characteristics - such as the high portability and the compatibility with multiple data formats - make it suitable for a broad range of research applications
Self-approaching Graphs
No full textIn this paper we introduce self-approaching graph drawings. A straight-line drawing of a graph is self-approaching if, for any origin vertex s and any destination vertex t, there is an st-path in the graph such that, for any point q on the path, as a point p moves continuously along the path from the origin to q, the Euclidean distance from p to q is always decreasing. This is a more stringent condition than a greedy drawing (where only the distance between vertices on the path and the destination vertex must decrease), and guarantees that the drawing is a 5.33-spanner.
We study three topics: (1) recognizing self-approaching drawings; (2) constructing self-approaching drawings of a given graph; (3)constructing a self-approaching Steiner network connecting a given set of points.
We show that: (1) there are efficient algorithms to test if a polygonal path is self-approaching in and , but it is NP-hard to test if a given graph drawing in has a self-approaching uv-path; (2) we can characterize the trees that have self-approaching drawings; (3) for any given set of terminal points in the plane, we can find a linear sized network that has a self-approaching path between any ordered pair of terminals