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
On Rectilinear Drawing of Graphs
No full textA rectilinear drawing is an orthogonal grid drawing without bends, possibly with edge crossings, without any overlapping between edges, between vertices, or between edges and vertices. Rectilinear drawings without edge crossings (planar rectilinear drawings) have been extensively investigated in graph drawing. Testing rectilinear planarity of a graph is NP-complete [10]. Restricted cases of the planar rectilinear drawing problem, sometimes called the “no-bend orthogonal drawing problem”, have been well studied (see, for example, [13,14,15]). In this paper, we study the problem of general non-planar rectilinear drawing; this problem has not received as much attention as the planar case. We consider a number of restricted classes of graphs and obtain a polynomial time algorithm, NP-hardness results, an FPT algorithm, and some bounds. We define a structure called a “4-cycle block”. We give a linear time algorithm to test whether a graph that consists of a single 4-cycle block has a rectilinear drawing, and draw it if such a drawing exists. We show that the problem is NP-hard for the graphs that consist of 4-cycle blocks connected by single edges, as well as the case where each vertex has degree 2 or 4. We present a linear time fixed-parameter tractable algorithm to test whether a degree-4 graph has a rectilinear drawing, where the parameter is the number of degree-3 and degree-4 vertices of the graph. We also present a lower bound on the area of rectilinear drawings, and a upper bound on the number of edges
Scaffold Hunter – Interactive Exploration of Chemical Space
No full textScaffold Hunter is a Java-based software tool for the analysis of structure-related biochemical data. It facilitates the interactive exploration of chemical space by enabling generation of and navigation in a scaffold tree hierarchy annotated with various data. The graphical visualization of structural relationships allows to analyze large data sets, e.g., to correlate chemical structure and biochemical activity
WiGis: A Framework for Scalable Web-Based Interactive Graph Visualizations
No full textTraditional network visualization tools inherently suffer from scalability problems, particularly when such tools are interactive and web-based. In this paper we introduce WiGis –Web-based Interactive Graph Visualizations. WiGis exemplify a fully web-based framework for visualizing large-scale graphs natively in a user’s browser at interactive frame rates with no discernible associated startup costs. We demonstrate fast, interactive graph animations for up to hundreds of thousands of nodes in a browser through the use of asynchronous data and image transfer. Empirical evaluations show that our system outperforms traditional web-based graph visualization tools by at least an order of magnitude in terms of scalability, while maintaining fast, high-quality interaction
An Improved Algorithm for the Metro-line Crossing Minimization Problem
No full textIn the metro-line crossing minimization problem, we are given a plane graph G = (V, E) and a set L of simple paths (or lines) that cover G, that is, every edge e ∈ E belongs to at least one path in L. The problem is to draw all paths in L along the edges of G such that the number of crossings between paths is minimized. This crossing minimization problem arises, for example, when drawing metro maps, in which multiple transport lines share parts of their routes. We present a new line-layout algorithm with O(|L|2 · |V |) running time that improves the best previous algorithms for two variants of the metro-line crossing minimization problem in unrestricted plane graphs. For the first variant, in which the so-called periphery condition holds and terminus side assignments are given in the input, Asquith et al. [1] gave an O(|L|3 · |E|2.5 )-time algorithm. For the second variant, in which all lines are paths between degree-1 vertices of G, Argyriou et al. [2] gave an O((|E| + |L|2 ) · |E|)-time algorithm
Drawing Directed Graphs Clockwise
No full textWe present a method for clockwise drawings of directed cyclic graphs. It is based on the eigenvalue decomposition of a skew-symmetric matrix associated with the graph and draws edges clockwise around the center instead of downwards, as in the traditional hierarchical drawing style. The method does not require preprocessing for cycle removal or layering, which often involves computationally hard problems. We describe an efficient algorithm which produces optimal solutions, and we present some application examples
Complexity of Some Geometric and Topological Problems
No full textWe show that recognizing intersection graphs of convex sets has the same complexity as deciding truth in the existential theory of the reals. Comparing this to similar results on the rectilinear crossing number and intersection graphs of line segments, we argue that there is a need to recognize this level of complexity as its own class
Semi-bipartite Graph Visualization for Gene Ontology Networks
No full textIn this paper we propose three layout algorithms for semibipartite graphs—bipartite graphs with edges in one partition—that emerge from microarray experiment analysis. We also introduce a method that effectively reduces visual complexity by removing less informative nodes. The drawing quality and running time are evaluated with five real-world datasets, and the results show significant reduction in crossing number and total edge length. All the proposed methods are available in visualization package GEOMI [1], and are well received by domain users
On the Perspectives Opened by Right Angle Crossing Drawings
No full textRight Angle Crossing (RAC) drawings are polyline drawings where each crossing forms four right angles. RAC drawings have been introduced because cognitive experiments provided evidence that increasing the number of crossings does not decrease the readability of the drawing if the edges cross at right angles. We investigate to what extent RAC drawings can help in overcoming the limitations of widely adopted planar graph drawing conventions, providing both positive and negative results. First, we prove that there exist acyclic planar digraphs not admitting any straight-line upward RAC drawing and that the corresponding decision problem is NP-hard. Also, we show digraphs whose straightline upward RAC drawings require exponential area. Second, we study if RAC drawings allow us to draw bounded-degree graphs with lower curve complexity than the one required by more constrained drawing conventions. We prove that every graph with vertex-degree at most 6 (at most 3) admits a RAC drawing with curve complexity 2 (resp. 1) and with quadratic area. Third, we consider a natural non-planar generalization of planar embedded graphs. Here we give bounds for curve complexity and area different from the ones known for planar embeddings
Succinct Greedy Drawings Do Not Always Exist
No full textA greedy drawing is a graph drawing containing a distance-decreasing path for every pair of nodes. A path (v0 , v1 , . . . , vm ) is distance-decreasing if d(vi , vm ) < d(vi−1 , vm ), for i = 1, . . . , m. Greedy drawings easily support geographic greedy routing. Hence, a natural and practical problem is the one of constructing greedy drawings in the plane using few bits for representing vertex Cartesian coordinates and using the Euclidean distance as a metric. We show that there exist greedy-drawable graphs that do not admit any greedy drawing in which the Cartesian coordinates have less than a polynomial number of bits