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
Drawing graphs with GLEE
No full textThis paper describes novel methods we developed to lay out graphs using Sugiyama's scheme [16] in a tool named GLEE. The main contributions are: a heuristic for creating a graph layout with a given aspect ratio, an efficient method of edge-crossings counting while performing adjacent vertex swaps, and a simple and fast spline routing algorithm
Crossing Numbers and Parameterized Complexity
No full textThe odd crossing number of G is the smallest number of pairs of edges that cross an odd number of times in any drawing of G. We show that there always is a drawing realizing the odd crossing number of G that uses at most 9^k crossings, where k is the odd crossing number of G. As a consequence of this and a result of Grohe we can show that the odd crossing number is fixed-parameter tractable
Improvement on the Decay of Crossing Numbers
No full textWe prove that the crossing number of a graph decays in a "continuous fashion" in the following sense. For any varepsilon>0 there is a delta>0 such that for n sufficiently large, every graph G with n vertices and mge n^1+varepsilon edges has a subgraph G' of at most (1-delta)m edges and crossing number at least (1-varepsilon)cro(G). This generalizes the result of J. Fox and Cs. Tóth
Maximum Upward Planar Subgraphs of Embedded Planar Digraphs
No full textThis paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: We prove that the addressed problem is NP-Hard; A fast heuristic and an exponential-time exact algorithm are described; A wide experimental analysis is performed to show the effectiveness of our techniques
Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices
No full textThis paper shows that any planar graph with vertices can be point-set embedded with at most one bend per edge on a universal set of points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge
Graph Drawing Contest Report
No full textThis report describes the 14th Annual Graph Drawing Contest, held in conjunction with the 2007 Graph Drawing Symposium in Sydney, Australia. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology
Computing Symmetries of Combinatorial Objects (Abstract)
No full textWe survey the practical aspects of computing the symmetries (automorphism) of combinatorial objects. These include all manner of graphs with adornments, matrices, point sets, etc.. Since automorphisms are just isomorphisms from an object to itself, the problem is intimately related to that of finding isomorphisms between two objects
Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
No full textLet C be a clustered graph and suppose that the planar embedding of its underlying graph is fixed. Is testing the c-planarity of easier than in the variable embedding setting? In this paper we give a first contribution towards answering the above question. Namely, we characterize c-planar embedded flat clustered graphs with at most five vertices per face and give an efficient testing algorithm for such graphs. The results are based on a more general methodology that shades new light on the c-planarity testing problem
A Note on Minimum-Area Straight-line Drawings of Planar Graphs
No full textDespite a long research effort, finding the minimum area for straight-line grid drawings of planar graphs is still an elusive goal. A long-standing lower bound on the area requirement for straight-line drawings of plane graphs was established in 1984 by Dolev, Leighton, and Trickey, who exhibited a family of graphs, known as nested triangles graphs, for which (2n/3-1) times (2n/3-1) area is necessary. We show that nested triangles graphs can be drawn in 2n^2/9 + O(n) area when the outer face is not given, improving a previous n^2/3 area upper bound. Further, we show that n^2/9 + Omega(n) area is necessary for any planar straight-line drawing of a nested triangles graph. Finally, we deepen our insight into the 4/9n^2-4/3n+1 lower bound by Dolev, Leighton, and Trickey, which is conjectured to be tight, showing a family of plane graphs requiring more area
Practical Level Planarity Testing and Layout with Embedding Constraints
No full textWe describe a practical method to test a leveled graph for level planarity and provide a level planar layout of the graph if the test succeeds, all in quadratic running-time. Embedding constraints restricting the order of incident edges around the vertices are allowed