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
Dynamic Spectral Layout of Small Worlds
No full textSpectral methods are naturally suited for dynamic graph layout, because continuous changes of edge weights yield continuous changes of the layout under very weak assumptions. We discuss some general principles for dynamic graph layout and derive a dynamic spectral layout approach for the animation of small-world models
Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs
No full textWe study parallel redrawing graphs: graphs embedded on moving point sets in such a way that edges maintain their slopes all throughout the motion. The configuration space of such a graph is of an oriented-projective nature, and its combinatorial structure relates to rigidity theoretic parameters of the graph. A special type of kinetic structure emerges, whose events can be analyzed combinatorially. Of particular interest are those planar graph
s which maintain non-crossing edges throughout the motion. Our main result is that they are (essentially) pseudo-triangulation mechanisms. These kinetic graph structures have potential applications in morphing of more complex shapes than just simple polygons
Mixed Upward Planarization - Fast and Robust
No full textIn a mixed upward drawing of a graph G=(V,E) all directed edges E_D \subseteq E are represented by monotonically increasing curves. Mixed upward drawings arise in applications like UML diagrams where such edges denote a hierarchical structure. [part of Introduction
Fast Node Overlap Removal
No full textMost graph layout algorithms treat nodes as points. The problem of node overlap removal is to adjust the layout generated by such methods so that nodes of non-zero width and height do not overlap, yet are as close as possible to their original positions. We give an O( n log n) algorithm for achieving this assuming that that the number of nodes overlapping any single node is bounded by some constant. This method has two parts, a constraint generation algorithm which generates a linear number of ``separation`` constraints and an
algorithm for finding a solution to these constraints ``close`` to the original node placement values. We also extend our constraint solving algorithm to give an active-set based algorithm which is guaranteed to find the optimal solution but which has considerably worse theoretical complexity. We compare our method with convex quadratic optimization and force-scan approaches and find that it is faster than either, gives results of better quality than force scan methods and similar quality to the quadratic optimisation approach
Hierarchical Layouts of Directed Graphs in Three Dimensions
No full textWe introduce a new graph drawing convention for 3D hierarchical drawings of directed graphs. The vertex set is partitioned into layers of vertices drawn in parallel planes. The vertex set is further partitioned into k>=2 subsets, called walls. The layout consists of a set of parallel walls which are perpendicular to the set of parallel planes of the layers. We also outline a method for computing such layouts and introduce four alternative algorithms for partitioning the vertex set into walls which address different aesthetic requirements
Energy-Based Clustering of Graphs with Nonuniform Degrees
No full textIn many real-world graphs, like social networks, hyperlink structures, and software dependency graphs, the degrees of the nodes vary widely. Finding clusters (i.e., dense subgraphs) in such graphs is of great practical interest, as these clusters may correspond to groups of friends or collaborators, semantically related documents, and cohesive software modules. Many existing clustering criteria and energy models are biased towards clustering together nodes with high degrees. In this paper, we develop a clustering criterion based on normalized cuts, and an energy model that uses edge repulsion instead of node repulsion to produce drawings that reveal clusters without this bias
An Application of Well-Orderly Trees in Graph Drawing
No full textWell-orderly trees seems to have the potential of becoming a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 4]. In this paper, we reduce the height of the visibility representation of plane graphs from 5n/6 to (4n-1)/5, by using well-orderly trees
Exact Crossing Minimization
No full textThe crossing number of a graph is the minimum number of edge crossings in any drawing of the graph into the plane. This very basic property has been studied extensively in the literature from a theoretic point of view and many bounds exist for a variety of graph classes. In this paper, we present the first algorithm able to compute the crossing number of general sparse graphs of moderate size and present computational results on a popular benchmark set of graphs. The approach uses a new integer linear programming formulation of the problem combined with strong heuristics and problem reduction techniques. This enables us to compute the crossing number for 91 percent of all graphs on up to 40 nodes in the benchmark set within a time limit of five minutes per graph
Two trees which are self-intersecting when drawn simultaneously
No full textAn actual topic in the graph drawing is the question how to draw two edge sets on the same vertex set, the so-called simultaneous drawing of graphs. The goal is to simultaneously find a nice drawing for both of the sets. It has been found out that only restricted classes of planar graphs can be drawn simultaneously using straight lines and without crossings within the same edge set. In this paper, we negatively answer one of the most often posted open questions namely whether any two trees with the same vertex set can be drawn simultaneously crossing-free in a straight line way
Drawing Graphs using Modular Decomposition
No full textIn this paper we present an algorithm for drawing an undirected graph G which takes advantage of the structure of the modular decomposition tree of G. Specifically, our algorithm works by traversing the modular decomposition tree of the input graph G on n vertices and m edges, in a bottom-up fashion until it reaches the root of the tree, while at the same time intermediate drawings are computed. In order to achieve aesthetically pleasing results, we use grid and circular placement techniques, and utilize an appropriate modification of a well-known spring embedder algorithm. It turns out,
that for some classes of graphs, our algorithm runs in O(n+m) time, while in general, the running time is bounded in terms of the processing time of the spring embedder algorithm. The result is a drawing that reveals the structure of the graph G and preserves certain aesthetic criteria