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
Layout of Directed Hypergraphs with Orthogonal Hyperedges (Extended Abstract)
No full textWe present a layout algorithm for directed hypergraphs. A hypergraph contains hyperedges that have multiple source and target nodes. Hyperedges are drawn with orthogonal segments. Nodes are organized in layers, so that for the majority of hyperedges the source nodes are placed in a higher layer than the target nodes, similar to traditional hierarchical layout [8,11]. The algorithm was implemented using ILOG JViews [10] for a project that targeted electrical signal visualization
Drawing Area-Proportional Venn and Euler Diagrams
No full textWe consider the problem of drawing Venn diagrams for which each regionrsquos area is proportional to some weight (e.g., population or percentage) assigned to that region. These area-proportional Venn diagrams have an enhanced ability over traditional Venn diagrams to visually convey information about data sets with interacting characteristics. We develop algorithms for drawing area-proportional Venn diagrams for any population distribution over two characteristics using circles and over three characteristics using rectangles and near-rectangular polygons; modifications of these algorithms are then presented for drawing the more general Euler diagrams. We present results concerning which population distributions can be drawn using specific shapes. A program to aid further investigation of area-proportional Venn diagrams is also described
Graph Drawing Contest Report
No full textThis report describes the Tenth Annual Graph Drawing Contest, held in conjunction with the 2003 Graph Drawing Symposium in Perugia, Italy. The purpose of the contest is to monitor and challenge the current state of the graph-drawing technology
Really Straight Graph Drawings
No full textWe study straight-line drawings of graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes, and that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). Drawings of non-planar graphs with few slopes are also considered. For example, it is proved that graphs of bounded degree and bounded treewidth have drawings with 0(log n) slopes.
Research initiated at the International Workshop on Fixed Parameter Tractability in Geometry and Games, organised by Sue Whitesides; Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 7-13, 2004. Research supported by NSERC and COMBSTRU
Building Blocks of Upward Planar Digraphs
No full textWe show that a digraph is upward planar if and only if its biconnected components have certain properties
A Note on the Self-similarity of Some Orthogonal Drawings
No full textLarge graphs are difficult to browse and to visually explore. This note adds up evidence that some graph drawing techniques, which produce readable layouts when applied to medium-size graphs, yield self-similar patterns when launched on huge graphs. To prove this, we consider the problem of assessing the self-similarity of graph drawings, and measure the box-counting dimension of the output of three algorithms, each using a different approach for producing orthogonal grid drawings with a reduced number of bends.
Work partially supported by European Commission – Fet Open project COSIN – COevolution and Self-organisation In dynamical Networks – IST-2001-33555, by European Commission – Fet Open project DELIS – Dynamically Evolving Large Scale Information Systems – Contract no 001907, by ldquoProgetto ALINWEB: Algoritmica per Internet e per il Webrdquo, MIUR Programmi di Ricerca Scientifica di Rilevante Interesse Nazionale, and by ldquoThe Multichannel Adaptive Information Systems (MAIS) Projectrdquo, MIUR Fondo per gli Investimenti della Ricerca di Base
No-Three-in-Line-in-3D
No full textThe no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. In 1951, Erdös proved that the answer is \Theta (n). We consider the analogous three-dimensional problem, and prove that the maximum number of points in the n × n × n grid with no three collinear is \Theta(n^2). This result is generalised by the notion of a 3D drawing of a graph. Here each vertex is represented by a distinct gridpoint in \mathbb{Z}^3, such that the line-segment representing each edge does not intersect any vertex, except for its own endpoints. Note that edges may cross. A 3D drawing of a complete graph K_n is nothing more than a set of n gridpoints with no three collinear. A slight generalisation of our first result is that the minimum volume for a 3D drawing of K_n is \Theta(n^3/2). This compares favourably to \Theta (n^3) when edges are not allowed to cross. Generalising the construction for K_n, we prove that every k-colourable graph on n vertices has a 3D drawing with O (n\sqrt{k}) volume. For the k-partite Turán graph, we prove a lower bound of \Omega((kn)^3/4).
Research supported by NSERC and COMBSTRU
A Compound Graph Layout Algorithm for Biological Pathways
No full textWe present a new compound graph layout algorithm based on traditional force-directed layout scheme with extensions for nesting and other application-specific constraints. The algorithm has been successfully implemented within Patika, a pathway analysis tool for drawing complicated biological pathways with compartmental constraints and arbitrary nesting relations to represent molecular complexes and pathway abstractions. Experimental results show that execution times and quality of the produced drawings with respect to commonly accepted layout criteria and pathway drawing conventions are quite satisfactory
Gravisto: Graph Visualization Toolkit
No full textGravisto, the Graph Visualization Toolkit, is more than a (Java-based) editor for graphs. It includes data structures, graph algorithms, several layout algorithms, and a graph viewer component. As a general toolkit for the visualization and automatic layout of graphs it is extensible with plug-ins and is suited for the integration in other Java-based applications
Intersection Reverse Sequences and Geometric Applications
No full textPinchasi and Radoicic [1] used the following observation to bound the number of edges in a topological graph with no self-intersecting cycles of length 4: if we make a list of the neighbors for every vertex in such a graph and order these lists cyclicly according to the connecting edge, then the common elements in any two lists have reversed cyclic order. Building on their work we give an estimate on the size of the lists having this property. As a consequence we get that a topological graph on n vertices not containing a self-intersecting C4 has O(n^3/2 log n) edges. Our result also implies that n pseudo-circles in the plane can be cut into O(n^3/2 log n) pseudo-segments, which in turn implies bounds on point-curve incidences and on the complexity of a level of an arrangement of curves