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
Approximate Proximity Drawings
No full textWe introduce and study a generalization of the well-known region of influence proximity drawings, called (ε1,ε2)-proximity drawings. Intuitively, given a definition of proximity and two real numbers ε1 ≥ 0 and ε2 ≥ 0, an (ε1,ε2)-proximity drawing of a graph is a planar straight-line drawing Γ such that: (i) for every pair of adjacent vertices u, v, their proximity region “shrunk” by the multiplicative factor 1:(1+ε1) does not contain any vertices of Γ; (ii) for every pair of non-adjacent vertices u, v, their proximity region “blown-up” by the factor (1+ε2) contains some vertices of Γ other than u and v. We show that by using this generalization, we can significantly enlarge the family of the representable planar graphs for relevant definitions of proximity drawings, including Gabriel drawings, Delaunay drawings, and β-drawings, even for arbitrarily small values of ε1 and ε2 . We also study the extremal case of (0,ε2)-proximity drawings, which generalizes the well-known weak proximity drawing model
Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings
No full textWe show that several problems of compacting orthogonal graph drawings to use the minimum number of rows or the minimum possible area cannot be approximated to within better than a polynomial factor in polynomial time unless P = NP. However, there is a fixed-parameter tractable algorithm for testing whether a drawing can be compacted to a given number of rows
Confluent Hasse Diagrams
No full textWe show that a transitively reduced digraph has a confluent
upward drawing if and only if its reachability relation has order dimen-
sion at most two. In this case, we construct a confluent upward drawing
with O(n2 ) features, in an O(n) × O(n) grid in O(n2 ) time. For the
digraphs representing series-parallel partial orders we show how to con-
struct a drawing with O(n) features in an O(n) × O(n) grid in O(n) time
from a series-parallel decomposition of the partial order. Our drawings
are optimal in the number of confluent junctions they use
Proportional Contact Representations of Planar Graphs
No full textWe study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees
Overloaded Orthogonal Drawings
No full textOrthogonal drawings are widely used for graph visualization due to their high clarity of representation. In this paper we present a technique called Overloaded Orthogonal Drawing. We first place the vertices on grid points following a relaxed version of dominance drawing, called weak dominance condition. Edge routing is implied automatically by the vertex coordinates. In order to simplify these drawings we use an overloading technique. All algorithms are simple and easy to implement and can be applied to directed acyclic graphs, planar, non-planar and also undirected graphs. We also present bounds on the number of bends and the area. Overloaded Orthogonal drawings present several interesting properties such as efficient visual edge confirmation as well as simplicity and clarity of the drawing
Shortest-Paths Preserving Metro Maps
No full textA metro map, or subway map, is a schematic representation of a metro system of a city. The main goal of a metro map is to provide a traveler with information on which lines to take to get from station A to station B, and at which stations he needs to switch lines. It is often not beneficial to use the geographical embedding of the system, but rather a representation where the relevant information is presented as clearly as possible. There are several algorithms that aim to generate such maps
Drawing Clustered Graphs as Topographic Maps
Get PDFThe visualization of clustered graphs is an essential tool for the analysis of networks, in particular, social networks, in which clustering techniques like community detection can reveal various structural properties. In this paper, we show how clustered graphs can be drawn as topographic maps, a type of map easily understandable by users not familiar with information visu- alization. Elevation levels of connected entities correspond to the nested structure of the cluster hierarchy. We present methods for initial node placement and describe a tree mapping based algorithm that produces an area efficient layout. Given this layout, a triangular ir- regular mesh is generated that is used to extract the elevation data for rendering the map. In addition, the mesh enables the routing of edges based on the topo- graphic features of the map
On Point-Sets That Support Planar Graphs
No full textA universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with n vertices, if bends on edges of the drawing are permitted, universal point-sets of size n are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be specified as part of the point-set, we prove that any planar graph with n vertices can be drawn on a universal set S of O(n2 / log n) points with at most one bend per edge and with the vertices and the bend points in S. If two bends per edge are allowed, we show that O(n log n) points are sufficient, and if three bends per edge are allowed, Θ(n) points are sufficient. When no bends on edges are permitted, no universal point-set of size o(n2 ) is known for the class of planar graphs.We show that a set of n points in balanced biconvex position supports
the class of maximum degree 3 series-parallel lattices
Upward Point Set Embeddability for Convex Point Sets Is in P
No full textIn this paper, we present a polynomial dynamic programming algorithm that tests whether a n-vertex directed tree T has an upward planar embedding into a convex point-set S of size n. We also note that our approach can be extended to the class of outerplanar digraphs. This nontrivial and surprising result implies that any given digraph can be efficiently tested for an upward planar embedding into a given convex point set
Accelerated Bend Minimization
No full textWe present an O(n3/2 ) algorithm for minimizing the number of bends in an orthogonal drawing of a plane graph. It has been posed as a long standing open problem at Graph Drawing 2003, whether the bound of O(n7/4 log n) shown by Garg and Tamassia in 1996 could be
improved. To answer this question, we show how to solve the uncapacitated min-cost flow problem on a planar bidirected graph with bounded costs and face sizes in O(n3/2 ) time