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
Force-Directed 3D Arc Diagrams
No full textWe discuss a force-directed algorithm for constructiong 3D arc diagrams. We introduce forces that allow curves in a 2D force directed graph to bow out and away from each other in the third dimension in order to achieve better angular resolutio
Untangling Hairballs
No full textSmall-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs. This is by design as the inherent objective of these methods is a globally uniform edge length or, more generally, accurate distance representation. The problem arises in graphs of high density or high conductance, and in the presence of high-degree vertices, all of which tend to pull vertices together and thus clutter variation in local density.
We here propose a method to draw online social networks, a special class of hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. To identify these ties we propose a novel measure of embeddedness. It is based on a weighted accumulation of triangles in quadrangles and can be determined efficiently. An evaluation on empirical and generated networks indicates that our approach improves upon previous methods using other edge indices. Although primarily designed to achieve more informative drawings, our spanning subgraph may also serve as a sparsifier that trims a hairball graph before the application of a clustering algorithm
Planar Octilinear Drawings with One Bend Per Edge
No full textIn octilinear drawings of planar graphs, every edge is drawn as an alternating sequence of horizontal, vertical and diagonal line-segments. In this paper, we study octilinear drawings of low edge complexity, i.e., with few bends per edge. A k-planar graph is a planar graph in which each vertex has degree less or equal to k. In particular, we prove that every 4-planar graph admits a planar octilinear drawing with at most one bend per edge on an integer grid of size O(n 2) ×O(n). For 5-planar graphs, we prove that one bend per edge still suffices in order to construct planar octilinear drawings, but in super-polynomial area. However, for 6-planar graphs we give a class of graphs whose planar octilinear drawings require at least two bends per edge
MapSets: Visualizing Embedded and Clustered Graphs
No full textWe describe MapSets, a method for visualizing embedded and clustered graphs. The proposed method relies on a theoretically sound geometric algorithm, which guarantees the contiguity and disjointness of the regions representing the clusters, and also optimizes the convexity of the regions. A fully functional implementation is available online and is used in a comparison with related earlier methods
Balanced Circle Packings for Planar Graphs
No full textWe study balanced circle packings and circle-contact representations for planar graphs, where the ratio of the largest circle’s diameter to the smallest circle’s diameter is polynomial in the number of circles. We provide a number of positive and negative results for the existence of such balanced configurations
Embedding Four-Directional Paths on Convex Point Sets
No full textA directed path whose edges are assigned labels “up”, “down”, “right”, or “left” is called four-directional, and three-directional if at most three out of the four labels are used. A direction-consistent embedding of an n-vertex four-directional path P on a set S of n points in the plane is a straight-line drawing of P where each vertex of P is mapped to a distinct point of S and every edge points to the direction specified by its label. We study planar direction-consistent embeddings of three- and four-directional paths and provide a complete picture of the problem for convex point sets
Graph Drawing Contest Report
No full textThis report describes the 21st Annual Graph Drawing Contest, held in conjunction with the 2014 Graph Drawing Symposium in Würzburg, Germany. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology
Anchored Drawings of Planar Graphs
No full textIn this paper we study the Anchored Graph Drawing (AGD) problem: Given a planar graph G, an initial placement for its vertices, and a distance d, produce a planar straight-line drawing of G such that each vertex is at distance at most d from its original position.
We show that the AGD problem is NP-hard in several settings and provide a polynomial-time algorithm when d is the uniform distance L ∞ and edges are required to be drawn as horizontal or vertical segments
