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
Edge Routing with Ordered Bundles
No full textWe propose a new approach to edge bundling. At the first stage we route the edge paths so as to minimize a weighted sum of the total length of the paths together with their ink. As this problem is NP-hard, we provide an efficient heuristic that finds an approximate solution. The second stage then separates edges belonging to the same bundle. To achieve this, we provide a new and efficient algorithm that solves a variant of the metro-line crossing minimization problem. The method creates aesthetically pleasing edge routes that give an overview of the global graph structure, while still drawing each edge separately, without intersecting graph nodes, and with few crossings
Pinning Balloons with Perfect Angles and Optimal Area
No full textWe study the problem of arranging a set of n disks with prescribed radii on n rays emanating from the origin such that two neighboring rays are separated by an angle of 2π/n. The center of the disks have to lie on the rays, and no two disk centers are allowed to lie on the same ray. We require that the disks have disjoint interiors, and that for every ray the segment between the origin and the boundary of its associated disk avoids the interior of the disks. Let r be the sum of the disk radii. We introduce a greedy strategy that constructs such a disk arrangement that can be covered with a disk centered at the origin whose radius is at most 2r, which is best possible. The greedy strategy needs O(n) arithmetic operations. As an application of our result we present an algorithm for embedding unordered trees with straight lines and perfect angular resolution such that it can be covered with a disk of radius n3.0367 , while having no edge of length smaller than 1. The tree drawing algorithm is an enhancement of a recent result by Duncan et al. [Symp. of Graph Drawing, 2010] that exploits the heavy-edge tree decomposition technique to construct a drawing of the tree that can be covered with a disk of radius 2n4
Visual Community Detection: An Evaluation of 2D, 3D Perspective and 3D Stereoscopic Displays
No full text3D drawing problems of the 90s were essentially restricted on representations in 3D perspective. However, recent technologies offer 3D stereoscopic representations of high quality which allow the introduction of binocular disparities, which is one of the main depth perception cues, not provided by the 3D perspective. This paper explores the relevance of stereoscopy for the visual identification of communities, which is a task of great importance in the analysis of social networks. A user study conducted on 35 participants with graphs of various complexity shows that stereoscopy outperforms 3D perspective in the vast majority of the cases. When comparing stereoscopy with 2D layouts, the response time is significantly lower for 2D but the quality of the results closely depend on the graph complexity: for a large number of clusters and a high probability of cluster overlapping stereoscopy outperforms 2D whereas for simple structures 2D layouts are more efficient
Right Angle Crossing Graphs and 1-Planarity
No full textA Right Angle Crossing Graph (also called RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A 1-planar graph is a graph that has a drawing where every edge is crossed at most once. We study the relationship between RAC graphs and 1-planar graphs in the extremal case that the RAC graphs have as many edges as possible. It is known that a maximally dense RAC graph with n > 3 vertices has 4n − 10 edges. We show that every maximally dense RAC graph is 1-planar. Also, we show that for every integer i such that i ≥ 0, there exists a 1-planar graph with n = 8 + 4i vertices and 4n − 10 edges that is not a RAC graph
Evaluating Partially Drawn Links for Directed Graph Edges
No full textWe investigate the readability of node-link diagrams for directed graphs when using partially drawn links instead of showing each link explicitly in its full length. Providing the complete link information between related nodes in a graph can lead to visual clutter caused by many edge crossings. To reduce visual clutter, we draw only partial links. Then, the question arises if such diagrams are still readable, understandable, and interpretable. As a step toward answering this question, we conducted a controlled user experiment with 42 participants to uncover differences in accuracy and completion time for three different tasks: identifying the existence of a direct link, the existence of an indirect connection with one intermediate node, and the node with the largest number of outgoing edges. Furthermore, we compared tapered and traditional edge representations, three different graph sizes, and six different link lengths. In all configurations, the nodes of the graph were placed according to the force-directed layout by Fruchterman and Reingold. One result of this study is that the characteristics of completion times and error rates depend on the type of task. A general observation is that
partially drawn links can lead to shorter task completion times, which occurs for nearly all graph sizes, tasks, and both tapered and traditional edge representations. In contrast, there is a tendency toward higher error rates for shorter links, which in fact is task-dependent
On the Page Number of Upward Planar Directed Acyclic Graphs
No full textIn this paper we study the page number of upward planar directed acyclic graphs. We prove that: (1) the page number of any n-vertex upward planar triangulation G whose every maximal 4-connected component has page number k is at most min{O(k log n), O(2k )}; (2) every upward planar triangulation G with o( n/log n) diameter has o(n) page number; and (3) every upward planar triangulation has a vertex ordering with o(n) page number if and only if every upward planar triangulation whose maximum degree is O(√n) does
Challenger, a New Way to Visualize Data
No full textChallenger is a software product that provides fast and online data visualization. This is done by visualizing data (graphs) as a network. Both force based and modularization algorithms are used and experimented with. Challenger facilitates fast and easy understanding of complex data. This is not only a matter of showing one ‘perfect’ visualization, but rather of letting users browse, analyze and ‘play’ visually with (subsets of) data interactively
Embedding Plane 3-Trees in ℝ2 and ℝ3
No full textA point-set embedding of a planar graph G with n vertices on a set P of n points in Rd , d ≥ 1, is a straight-line drawing of G, where the vertices of G are mapped to distinct points of P . The problem of computing a point-set embedding of G on P is NP-complete in R2 , even when G is 2-outerplanar and the points are in general position. On the other hand, if the points of P are in general position in R3 , then any bijective mapping of the vertices of G to the points of P determines a point-set embedding of G on P . In this paper, we give an O(n4/3+ )-expected time algorithm to decide whether a plane 3-tree with n vertices admits a point-set embedding on a given set of n points in general position in R2 and compute such an embedding if it exists, for any fixed >0. We extend our algorithm to embed a subclass of 4-trees on a point set in R3 in the form of nested tetrahedra. We also prove that given a plane 3-tree G with n vertices, a set P of n points in R3 that are not necessarily in general position and a mapping of the three outer vertices of G to three different points of P , it is NP-complete to decide if G admits a point-set embedding on P respecting the given mapping
How to Visualize the K-Root Name Server (Demo)
No full textWe present a system that visualizes the evolution of the service provided by one of the most popular root name servers, called K-root, operated by the RIPE Network Coordination Centre (RIPE NCC) and distributed in several locations (instances) worldwide. The system can be used either to monitor what happened during a prescribed time interval or to observe the status of the service in near real-time. The system visualizes how and when the clients of K-root migrate from one instance to another, how the number of clients associated with each instance changes over time, and what are the instances that contribute to offer the service to a selected Internet Service Provider. In addition, the visualization aims at distinguishing usual from unusual operational patterns. This helps not only to improve the quality of the service but also to spot security-related issues and to investigate unexpected routing changes
Upper Bound Constructions for Untangling Planar Geometric Graphs
No full textFor every n ∈ N, there is a straight-line drawing Dn of a planar graph on n vertices such that in any crossing-free straight-line drawing of the graph, at most O(n.4982 ) vertices lie at the same position as in Dn . This improves on an earlier bound of O( √ n) by Goaoc et al