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
SDE: Graph Drawing Using Spectral Distance Embedding
No full textWe present a novel graph drawing algorithm which uses a spectral decomposition of the distance matrix to approximate the graph theoretical distances. The algorithm preserves symmetry and node densities, i.e., the drawings are aesthetically pleasing. The runtime for typical 20,000 node graphs ranges from 100 to 150 seconds
Graph Treewidth and Geometric Thickness Parameters
No full textConsider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness t(G). By restricting the edges to be straight, we obtain the geometric thickness gt(G). By further restricting the vertices to be in convex position, we obtain the book thickness _t(G). This paper studies the relationship between these parameters and the treewidth of G. Let T_k denote the class of graphs with treewidth at most k. Let t{T_k} / gt{T_k} / _t{T_k} denote the maximum thickness / geometric thickness / book thickness of a graph in T_k. We prove that
: t{T_k}=gt{T_k}=ceil{k/2}, and _t{T_k}=k for k=3. The first result says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. The second result disproves the conjecture of Ganley and Heath [Discrete Appl. Math. 2001] that _t{T_k}=k for all k. Analogous results are proved for outerthickness, arboricity, and star-arboricity
A Hybrid Model for Drawing Dynamic and Evoling Graphs
No full textDynamic processes frequently occur in many applications. Visualizations of dynamically evolving data, for example as part of the data analysis, are typically restricted to a cumulative static view or an animation/sequential view. Both methods have their benefits and are often complementary in their use. In this article, we present a hybrid model that combines the two techniques. This is accomplished by 2.5D drawings which are calculated in an incremental way. The method has been evaluated on collaboration networks
GEOMI: GEOmetry for Maximum Insight
No full textThis paper describes the GEOMI system, a visual analysis tool for the visualisation and analysis of large and complex networks. GEOMI provides a collection of network analysis methods, graph layout algorithms and several graph navigation and interaction methods. GEOMI is a new generation of visual analysis tools combining graph visualisation techniques with network analysis methods. GEOMI is available from http://www.cs.usyd.edu.au/~visual/valacon
Volume Requirements of 3D Upward Drawings
No full textThis paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model, and so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the special case of rooted trees a linear volume upper bound is achievable
Incremental Connector Routing
No full textMost diagram editors and graph construction tools provide some form of automatic connector routing, typically providing orthogonal or poly-line connectors. Usually the editor provides an initial automatic route when the connector is created and then modifies this when the connector end-points are moved. None that we know of ensure that the route is of minimal length while avoiding other objects in the diagram. We study the problem of incrementally computing minimal length object-avoiding poly-line connector routings. Our algorithms are surprisingly fast and allow us to recalculate optimal connector routings fast enough to reroute connectors even during direct manipulation of an object`s position, thus giving instant feedback to the diagram author
MultiPlane: A New Framework for Drawing Graphs in Three Dimensions
No full textThis poster presents a new framework for drawing graphs in three dimensions, which can be used effectively to visualise large and complex real wordl networks
On Straightening Low-Diameter Unit Trees
No full textA polygonal chain is a sequence of consecutively joined edges embedded in space. A k-chain is a chain of k edges. A polygonal tree is a set of edges joined into a tree structure embedded in space. A unit tree is a tree with only edges of unit lenght. A chain or a tree is simple if non-adjacent edges do not intersect. ..
Trémaux trees and planarity
No full textWe present a simplified version of the DFS-based Left-Right planarity testing and embedding algorithm implemented in Pigale which has been considered as the fastest implemented one [J.M. Boyer, P.F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: implementing fast and simple DFS-based planarity and embedding algorithm. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 25-36. Springer, 2004.].
We give here a simple full justification of the algorithm, based on a preliminary extended study of topological properties of DFS trees
Morphing Planar Graphs While Preserving Edge Directions
No full textTwo straight-line drawings P,Q of a graph (V,E) are called parallel if, for every edge (u,v) in E, the vector from u to v has the same direction in both P and Q. We study problems of the form: given simple, parallel drawings P,Q does there exist a continuous transformation between them such that intermediate drawings of the transformation remain simple and parallel with P (and Q)? We prove that a transformation can always be found in the case of orthogonal drawings; however, when edges are allowed to be in one of three or more slopes the problem becomes NP-hard