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
A Layout Algorithm for Signaling Pathways
No full textVisualization is crucial to the effective analysis of biological pathways. A poorly laid out pathway confuses the user, while a well laid out one improves the user’s comprehension of the underlying biological phenomenon.
We present a new, elegant algorithm for layout of biological signaling pathways. Our algorithm uses a force-directed layout scheme, taking into account directional and rectangular regional constraints enforced by different molecular interaction types and subcellular locations in a cell. The algorithm has been successfully implemented as part of a pathway visualization and analysis toolkit named Patika, and results with respect to computational complexity and quality of the layout have been found satisfactory. The algorithm may be easily adapted to be used in other applications with similar conventions and constraints as well.
Patika version 1.0 beta is available upon request at http://www.patika.org
Complexity Results for Three-dimensional Orthogonal Graph Drawing
No full textWe introduce the 3SAT reduction framework which can be used to prove the NP-hardness of finding three-dimensional orthogonal drawings with specific constraints. We use it to show that finding a drawing of a graph whose edges have a fixed shape is NP-hard. Also, it is NP-hard finding a drawing of a graph with nodes at prescribed positions when a maximum of two bends per edge is allowed. We comment the impact of these results on the two open problems of determining whether a graph always admits a 3D orthogonal drawing with at most two bends per edge and of characterizing orthogonal shapes admitting a drawing without intersections
On Rectilinear Duals for Vertex-Weighted Plane Graphs
No full textLet G = (V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of G is a partition of a rectangle into |V| simple rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in E. A rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant
Drawing K_n in Three Dimensions with One Bend per Edge
No full textWe give a drawing of K_n in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n^{2.5}). This represents a significant improvement over previous drawings in this model
Delta-confluent Drawings
No full textWe generalize the tree-confuent graphs to a broader class of graphs called delta-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some results about the visualization of delta-confuent graphs are also given
Transversal structures on triangulations, with application to straight-line drawing
No full textWe define and study a structure called transversal edge-partition related to triangulations without non empty triangles, which is equivalent to the regular edge labeling discovered by Kant and He. We study other properties of this structure and show that it gives rise to a new straight-line drawing algorithm for triangulations without non empty triangles, and more generally for 4-connected plane graphs with at least 4 border vertices. Taking uniformly at random such a triangulation with 4 border vertices and n vertices, the size of the grid is almost surely frac{n}{2}cdotleft( 1-frac{5}{27} ight) imes frac{n}{2}cdotleft( 1-frac{5}{27} ight) up to fluctuations of order sqrt{n}, and the half-perimeter is bounded by n-1. The best previously known algorithms for straight-line drawing of such triangulations only guaranteed a grid of size (lceil n/2 ceil -1) imes lfloor n/2 floor. The reduction-factor of frac{5}{27} can be explained thanks to a new bijection between ternary trees and triangulations of the 4-gon without non empty triangles
On Balloon Drawings of Rooted Trees
No full textAmong various styles of tree drawing reported in the literature, balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. Each subtree in the balloon drawing of a tree is enclosed in a circle. The radius of each circle is proportional to the number of descendents associated with the root node of the subtree. In this paper, we investigate various issues related to balloon drawing of rooted trees from both algorithmic and practical viewpoints. First, we design an efficient algorithm to optimize angular resolution and aspect ratio for the balloon drawing of rooted unordered trees. For the case of ordered trees for which the center of the enclosing circle of a subtree need not coincide with the root of the subtree, flipping the drawing of a subtree (along the axis from the parent to the root of the subtree) might change both the aspect ratio and the angular resolution of the drawing. We show that optimizing the angular resolution as well as the aspect ratio with respect to this type of rooted ordered trees is reducible to the perfect matching problem for bipartite graphs, which is solvable in polynomial time. Aside from studying balloon drawing from an algorithmic viewpoint, we also propose a local magnetic spring model (which can be thought of as a variant of the popular force-directed strategies) for producing dynamic balloon drawings for rooted trees. In our framework, each edge is modelled by a magnetized spring, while each vertex is placed on a local polar magnetic field which does not interact with other magnetic fields. Our approach facilitates various operations, including interaction and navigation, on trees. With a slight modification to our force-directed based balloon drawing algorithm, we are able to apply our work to the drawing of galaxy systems, H-trees, and sparse graphs, which are of practical interest
Convex Drawings of Plane Graphs of Minimum Outer Apices
No full textIn a convex drawing of a plane graph G, every facial cycle of G is drawn as a convex polygon. A polygon for the outer facial cycle is called an outer convex polygon. A necessary and sufficient condition for a plane graph G to have a convex drawing is known. However, it has not been known how many apices of an outer convex polygon are necessary for G to have a convex drawing. In this paper, we show that the minimum number of apices of an outer convex polygon necessary for G to have a convex drawing is, in effect, equal to the number of leaves in a triconnected component decomposition tree of a new graph constructed from G, and that a convex drawing of G having the minimum number of apices can be found in linear time
A Mixed-Integer Program for Drawing High-Quality Metro Maps
No full textIn this paper we investigate the problem of drawing metro maps which is defined as follows. Given a planar graph G of maximum degree 8 with its embedding and vertex locations (e.g. the physical location of the tracks and stations of a metro system) and a set mathcal L of paths or cycles in G (e.g. metro lines) such that each edge of G belongs to at least one element of mathcal L, draw G and mathcal L emph{nicely}. We first specify the niceness of a drawing by listing a number of hard and soft constraints. Then we present a mixed-integer program (MIP) which always finds a drawing that fulfills all hard constraints (if such a drawing exists) and optimizes a weighted sum of costs corresponding to the soft constraints. We also describe some heuristics that speed up the MIP. We have implemented both the MIP and the heuristics. We compare their output to that of previous algorithms for drawing metro maps and to official metro maps drawn by graphic designers
Minimum Depth Graph Embeddings and Quality of the Drawings: an Experimental Analysis
No full textThe depth of a planar embedding of a graph is a measure of the topological nesting of the biconnected components of the graph in that embedding. Motivated by the intuition that lower depth values lead to better drawings, previous works proposed efficient algorithms for finding embeddings with minimum depth. We present an experimental study that shows the impact of embedding depth minimization on important aesthetic criteria and relates the effectiveness of this approach with measures of how much the graph resembles a tree or a biconnected graph. In our study, we use a well known test suite of graphs obtained from real-world applications and a randomly generated one with favorable biconnectivity properties. In the experiments we consider orthogonal drawings computed using the topology-shape-metrics approach