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
3D Visualization of Semantic Metadata Models and Ontologies
No full textWe propose an algorithm for the 3D visualization of general ontology models used in many applications, such as semantic web, entity-relationship diagrams and other database models. The visualization places entities in the 3D space. Previous techniques produce drawings that are 2-dimensional, which are often complicated and hard to comprehend. Our technique uses the third dimension almost exclusively for the display of the isa relationships (links) while the property relationships (links) are placed on some layer (plane). Thus the semantic difference between isa links and property links, which should be as vertical or as horizontal as possible respectively, is emphasized. Special reference is made on a certain model, the CIDOC Conceptual Reference Model.
This work was supported in part by INFOBIOMED code: IST-2002-507585 and the Greek General Secretariat for Research and Technology under Program ldquoARISTEIArdquo, Code 1308/B1/3.3.1/317/12.04.2002
DNA Secondary Structures for Probe Design
No full textVisualizing DNA secondary structures is essential to fast and efficient design of probes for DNA chips. There are several programs available for visualizing single-stranded RNA secondary structures, but these programs cannot be used to draw DNA secondary structures formed by several hundred to thousand primers and target genes. We have developed an algorithm and program for visualizing DNA secondary structures formed by multiple strands. We believe the program will be a valuable tool for designing primers and probes in DNA chips.
This work was supported by the Korea Science and Engineering Foundation (KOSEF) under grant R01-2003-000-10461-0
An Experimental Study of Crossing Minimization Heuristics
No full textWe present an extensive experimental study of heuristics for crossing minimization. The heuristics are based on the planarization approach, so far the most successful framework for crossing minimization. We study the effects of various methods for computing a maximal planar subgraph and for edge re-insertion including post-processing and randomization
More Efficient Generation of Plane Triangulations
No full textIn this paper we give an algorithm to generate all biconnected plane triangulations having exactly n vertices including exactly r vertices on the outer face. The algorithm uses O(n) space in total and generates such triangulations without duplications in O(rn) time per triangulation, while the previous best algorithm generates such triangulations in O(r^{2}n) time per triangulation
Planar Embeddings of Graphs with Specified Edge Lengths
No full textWe consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the planarity restrictions, which has close connections to rigidity theory, and where it is easy to see that the problem is NP-hard. In contrast, we show that the problem is tractable—indeed, solvable in linear time on a real RAM—for planar embeddings of planar 3-connected triangulations, even if the outer face is not a triangle. This result is essentially tight: the problem becomes NP-hard if we consider instead planar embeddings of planar 3-connected infinitesimally rigid graphs, a natural relaxation of triangulations in this context
BGPlay: A System for Visualizing the Interdomain Routing Evolution (Long Demo)
No full textIn this paper we describe the visual interface of BGPlay, an on-line service for the visualization of the behavior and of the instabilities of the Internet routing at the autonomous system level.
A graph showing only connections among autonomous systems is not enough to convey all the information needed to fully understand the routing and its changes. BGPlay provides specifically tailored techniques and algorithms to show the routing at specific instants of time and to animate its changes. The system obtains routing data from well known on-line archives of routing information constantly kept up-to-date
An Improved Approximation to the One-Sided Bilayer Drawing
No full textGiven a bipartite graph G=(V,W,E), a bilayer drawing consists of placing nodes in the first vertex set V on a straight line L_1 and placing nodes in the second vertex set W on a parallel line L_2. The one-sided crossing minimization problem asks to find an ordering of nodes in V to be placed on L_1 so that the number of arc crossings is minimized. In this paper, we prove that there always exits a solution whose crossing number is at most 1.4664 times of a well-known lower bound that is obtained by summing up min{c_{uv}, c_{vu}} over all node pairs u, v \epsilon V, where c_uv denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering
Selected Open Problems in Graph Drawing
No full textIn this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing
Convex Drawings of 3-Connected Plane Graphs (Extended Abstract)
No full textWe use Schnyder woods of 3-connected planar graphs to produce convex straight line drawings on a grid of size (n-2-\Delta) x (n-2-\Delta). The parameter \Delta >= 0 depends on the the Schnyder wood used for the drawing. This parameter is in the range 0 <= \Delta <= \frac{n}{2} - 2
Dynamic Graph Drawing of Sequences of Orthogonal and Hierarchical Graphs
No full textIn this paper we introduce two novel algorithms for drawing sequences of orthogonal and hierarchical graphs while preserving the mental map. Both algorithms can be parameterized to trade layout quality for dynamic stability. In particular, we had to develop new metrics which work upon the intermediate results of layout phases. We discuss some properties of the resulting animations by means of examples