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
Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
No full textWe present a polynomial-time algorithm for c-planarity testing of clustered graphs with fixed plane embedding and such that every cluster induces a subgraph with at most two connected components
An Experimental Study on Distance-Based Graph Drawing
No full textIn numerous application areas, general undirected graphs need to be drawn, and force-directed layout appears to be the most frequent choice. We present an extensive experimental study showing that, if the goal is to represent the distances in a graph well, a combination of two simple algorithms based on variants of multidimensional scaling is to be preferred because of their efficiency, reliability, and even simplicity. We also hope that details in the design of our study help advance experimental methodology in algorithm engineering and graph drawing, independent of the case at hand
On the Hardness of Orthogonal-Order Preserving Graph Drawing
No full textThere are several scenarios in which a given drawing of a graph is to be modified subject to preservation constraints. Examples include shape simplification, sketch-based, and dynamic graph layout. While the orthogonal ordering of vertices is a natural and frequently called for preservation constraint, we show that, unfortunately, it results in severe algorithmic difficulties even for the simplest graphs. More precisely, we show that orthogonal-order preserving rectilinear and uniform edge length drawing is N P -hard even for paths
Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
No full textA graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G − e is 1-planar for every edge e of G. We construct two infinite families of minimal non-1-planar graphs and show that for every integer n ≥ 63, n 54 there are at least 2 4 − 4 non-isomorphic minimal non-1-planar graphs of order n. It is also proved that testing 1-planarity is NP-complete. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves
a question of Hlineny
Drawing (Complete) Binary Tanglegrams
No full textA binary tanglegram is a pair S, T of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a drawing with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for general binary trees. We show thatthe problem is hard even if both trees are complete binary trees. For this case we give an O(n3 )-time 2-approximation and a new and simple fixed-parameter algorithm. We show that the maximization version of the dual problem for general binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation
Rapid Multipole Graph Drawing on the GPU
No full textAs graphics processors become powerful, ubiquitous and easier to program, they have also become more amenable to general purpose high-performance computing, including the computationally expensive task of drawing large graphs. This paper describes a new parallel analysis of the multipole method of graph drawing to support its efficient GPU implementation. We use a variation of the Fast Multipole Method to estimate the long distance repulsive forces in force directed layout. We support these multipole computations efficiently with a k-d tree constructed and traversed on the GPU. The algorithm achieves impressive speedup over previous CPU and GPU methods, drawing graphs with hundreds of thousands of vertices within a few seconds via CUDA on an NVIDIA GeForce 8800 GTX
Topology Preserving Constrained Graph Layout
No full textConstrained graph layout is a recent generalisation of force-directed graph layout which allows constraints on node placement. We give a constrained graph layout algorithm that takes an initial feasible layout and improves it while preserving the topology of the initial layout. The algorithm supports poly-line connectors and clusters. During layout the connectors and cluster boundaries act like impervious rubber-bands which try to shrink in length. The intended application for our algorithm is dynamic graph layout, but it can also be used to improve layouts generated by other graph layout techniques
Two Polynomial Time Algorithms for the Metro-Line Crossing Minimization Problem
No full textThe metro-line crossing minimization (MLCM) problem was recently introduced as a response to the problem of drawing metro maps or public transportation networks, in general. According to this problem, we are given a planar, embedded graph G=(V,E)and a set L of simple paths on G, called lines. The main task is to place the lines on G, so that the number of crossings among pairs of lines is minimized.
Our main contribution is two polynomial time algorithms. The first solves the general case of the MLCM problem, where the lines that traverse a particular vertex of G are allowed to use any side of it to either ``enter'' or ``exit'', assuming that the endpoints of
the lines are located at vertices of degree one. The second one solves more efficiently the restricted case, where only the left and the right side of each vertex can be used.
To the best of our knowledge, this is the first time where the general case of the MLCM problem is solved. Previous work was devoted to the restricted case of the MLCM problem under the additional assumption that the endpoints of the lines are either the topmost or the bottommost in their corresponding vertices, i.e.,they are either on top or below the lines that pass through the vertex. Even for this case, we improve a known result of Asquith et al. from to
Clustered Planarity: Clusters with Few Outgoing Edges
No full textWe present a linear algorithm for c-planarity testing of clustered graphs, in which every cluster has at most four outgoing edges
3-Regular non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces
No full textThe Four Color Theorem is equivalent with its dual form stating that each 2-edge-connected 3-regular planar graph is 3-edgecolorable. In 1968, Grünbaum conjectured that similar property holds true for any orientable surface, namely that each 3-regular graph with a polyhedral embedding in an orientable surface has a 3-edge-coloring. Note that an embedding of a graph in a surface is called polyhedral if its geometric dual has no multiple edges and loops. We present a negative solution of this conjecture, showing that for each orientable surface of genus at least 5, there exists a 3-regular non 3-edge-colorable
graph with a polyhedral embedding in the surface