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
Planarity Testing and Optimal Edge Insertion with Embedding Constraints
No full textMany practical applications demand additional restrictions on an admissible
planar embedding. In particular, constraints on the permitted (clockwise) order
of the edges around a vertex, like so-called side constraints, abound.
In this paper, we introduce a set of hierarchical embedding constraints that
also comprises side constraints. We present linear time algorithms for testing
if a graph is ec-planar, i.e., admits a planar embedding satisfying the
given embedding constraints, as well as for computing such an embedding.
Moreover, we characterize the set of all possible ec-planar embeddings and
consider the problem of finding a planar combinatorial embedding of a planar
graph such that an additional edge can be inserted with the minimum number of
crossings; we show that this problem can still be solved in linear time under
the additional restrictions of embedding constraints
Visualizing Large and Clustered Networks
No full textThe need to visualize large and complex networks has strongly increased in the last
decade. Although networks with more than 1000 vertices seem to be prohibitive for a comprehensive layout,
real-world networks exhibit a very inhomogenous edge density that can be harnessed to derive an aesthetic and
structured layout. Here, we will present a heuristic that finds a spanning tree
with a very low average spanner property for the non-tree edges,
the so-called "backbone" of a network.
This backbone can then be used to apply a modified tree-layout algorithm to draw the whole graph in a way that highlights dense parts of the graph, so-called
clusters, and their inter-connections
Partitioned Drawings
No full textIn this paper we consider the problem of creating partitioned
drawings of graphs G=(V,E). In a partitioned drawing each vertex is placed
inside a given partition cell of a rectangular partition of the
drawing area. This problem has several applications in practice,
e.g. for UML activity diagrams or wiring schematics. We first
formalize the problem and analyze its complexity. Then we give a
heuristic approach which is based on the topology-shape-metrics approach
and produces partitioned drawings in time
O((|V|+c)^2 log (|V|+c)), where c denotes the number of crossings
Path Simplification for Metro Map Layout
No full textWe investigate the problem of creating simplified representations of
polygonal paths. Specifically, we look at a path simplification
problem in which line segments of a simplification are required to
conform with a restricted set of directions C. An algorithm is
given to compute such simplified paths in O(|C|^3 n^2) time,
where n is the number of vertices in the original path. This
result is extended to produce an algorithm for graphs induced by
multiple intersecting paths. The algorithm is applied to construct
schematised representations of real world railway networks, in the
style of metro maps
How to Embed a Path onto Two Sets of Points
No full textLet R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let P be a path such that |R| vertices of P are red and |B| vertices of P are blue. We study the problem of computing a crossing-free drawing of P such that each blue vertex is represented as a point of B and each red vertex of P is represented as a point of R. We show that such a drawing can always be realized by using at most one bend per edge
Drawing Clustered Graphs in Three Dimensions
No full textClustered graphs are very useful model for drawing large and complex networks. This paper presents a new method for drawing clustered graphs in three dimensions. The method uses a divide and conquer approach. More specifically, it draws each cluster in a 2D plane to minimise occlusion and ease navigation. Then a 3D drawing of the whole graph is constructed by combining these 2D drawings. Our main contribution is to develop three linear time weighted tree drawing algorithms in three dimensions for clustered graph layout. Further, we have implemented a series of six different layouts for clustered graphs by combining three 3D tree layouts and two 2D graph layouts. The experimental results with metabolic pathways show that our method can produce a nice drawing of a clustered graph which clearly shows visual separation of the clusters, as well as highlighting the relationships between the clusters. Sample drawings are available from http://www.cs.usyd.edu.au/~visual/valacon/gallery/C3D
Stress Majorization with Orthogonal Ordering Constraints
No full textThe adoption of the stress-majorization method from multi-dimensional scaling into graph layout has provided an improved mathematical basis and better convergence properties for so-called ``force-directed placement`` techniques. In this paper we give an algorithm for augmenting such stress-majorization techniques with orthogonal ordering constraints and we demonstrate several graph-drawing applications where this class of constraints can be very useful
D-Dupe: An Interactive Tool for Entity Resolution in Social Networks
No full textGraphs describing real world data often contain duplicate entries for names, cities, or other entities. This paper presents D-Dupe, an interactive visualization tool designed to help users to discover and resolve duplicate nodes in a social network. Users can resolve the nodes are in fact distinct. The entity resolution process is iterative; as pairs of nodes are merged, additional duplicates may become apparent
Regular embeddings of multigraphs
No full textWe prove that the vertex set of any twin-free multigraph G has an embedding into some point set P of some Euclidean space Rk, such that the automorphism group of G is isomorphic to the isometry group of Rk globally preserving P
Crossings and Permutations
No full textWe investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation pi which minimizes the number of crossings. This is known as the Kemeny optimal aggregation problem minimizing the Kendall-tau distance. Recent interest into this problem comes from application to meta-search and spam reduction on the Web. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. Here we introduce the max-version of the crossing minimization problem, PCM_{max}-k, which attempts to minimize the discrimination against any permutation. We show the NP-hardness of the common and the max version for k >= 4 permutations (and k even), and establish a 2-2/k and a 2-approximation, respectively. For two permutations the problem is solved merely by inspecting the drawings, whereas it remains open for three permutations