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
Eigensolver Methods for Progressive Multidimensional Scaling of Large Data
No full textWe present a novel sampling-based approximation technique for
classical multidimensional scaling that yields an extremely fast
layout algorithm suitable even for very large graphs. It produces
layouts that compare favorably with other methods for drawing large
graphs, and it is among the fastest methods available. In addition,
our approach allows for progressive computation, i.e. a rough
approximation of the layout can be produced even faster, and then be
refined until satisfaction
On the Decay of Crossing Numbers
No full textThe crossing number \cn(G) of a graph G is the minimum number of crossings over all drawings of G in the plane. In 1993, Richter and Thomassen [13] conjectured that there is a constant c such that every graph G with crossing number k has an edge e such that \cn(G-e) \geq k-c\sqrt{k}. They showed only that G always has an edge e with \cn(G-e) \geq \frac{2}{5}\cn(G)-O(1). We prove that for every fixed \epsilon>0, there is a constant n_0 depending on \epsilon such that if G is a graph with n>n_0 vertices and m>n^{1+\epsilon} edges, then G has a subgraph G' with at most (1-\frac{1}{24\epsilon})m edges such that \cn(G') \geq (\frac{1}{28}-o(1))\cn(G)
On the Crossing Number of Almost Planar Graphs
No full textCrossing minimization is one of the most challenging algorithmic
problems in topological graph theory, with strong ties to graph
drawing applications. Despite a long history of intensive research,
no practical "good" algorithm for crossing minimization is known
(that is hardly surprising, since the problem itself is NP-complete).
Even more surprising is how little we know about a seemingly simple
particular problem: to minimize the number of crossings in an
almost planar graph, that is, a graph
with an edge whose removal leaves a planar graph. This
problem is in turn a building block in an
"edge insertion" heuristic for crossing minimization.
In this paper we prove a constant factor approximation algorithm for
the crossing number of almost planar graphs with bounded degree.
On the other hand, we demonstrate nontriviality of the crossing minimization
problem on almost planar graphs by exhibiting several examples,
among them new families of crossing critical graphs which are almost planar
and projective
Drawing cubic graphs with at most five slopes
No full textWe show that every graph G with maximum degree three
has a straight-line drawing in the plane using edges
of at most five different slopes. Moreover, if G is
connected and has at least one vertex of degree less
than three, then four directions suffice
Thickness of Bar 1-Visibility Graphs
No full textBar k-visibility graphs are graphs admitting a representation in
which the vertices correspond to horizontal line segments, called
bars, and the edges correspond to vertical lines of sight which can
traverse up to k bars. These graphs were introduced by Dean et
al. [3] who conjectured that bar 1-visibility graphs have
thickness at most 2. We construct a bar 1-visibility graph having
thickness 3, disproving their conjecture. For a special case of bar
1-visibility graphs we present an algorithm partitioning the edges
into two plane graphs, showing that for this class the thickness is
indeed bounded by 2
Radial Drawings of Graphs: Geometric Constraints and Trade-offs
No full textThis paper studies how to compute radial drawings of graphs by
taking into account additional geometric constraints which
correspond to typical aesthetic and semantic requirements for the
visualization. The following requirements are considered: vertex
centrality, edge crossings, curve complexity, and vertex radial
distribution. Trade-offs among these requirements and efficient
drawing algorithms are presented
Drawing Bipartite Graphs on Two Curves
No full textLet G be a bipartite graph, and let be two
parallel convex curves; we study the question about whether G
admits a planar straight line drawing such that the vertices of
one partite set of G lie on and the vertices of the
other partite set lie on . A characterization is
presented that gives rise to linear time testing and drawing
algorithms
Improved circular layouts
No full textCircular graph layout is a drawing scheme where all nodes
are placed on the perimeter of a circle.
An inherent issue with circular layouts
is that the rigid restriction on node placement often gives rise to long
edges and an overall dense drawing. We suggest here three independent,
complementary techniques for lowering the density and improving the
readability of circular layouts. First, a new algorithm is given for placing thenodes on the circle such that edge lengths are reduced. Second, we enhance
the circular drawing style by allowing some of the edges to be routed around
the exterior of the circle. This is accomplished with an algorithm for
optimally selecting such a set of externally routed edges. The third
technique reduces density by coupling groups of edges as bundled splines that
share part of their route. Together, these techniques are able to
reduce clutter, density and crossings compared with existing methods
Fast Node Overlap Removal - Correction
No full textOur recent paper [1] details an algorithm
for removing overlap between rectangles, while attempting to displace the
rectangles by as little as possible. The algorithm is primarily motivated by
the node-overlap removal problem in graph drawing
THE DULMAGE-MENDELSOHN PRECONDITIONING OF DECAY CHAINS
Get PDFThe uses of the Dulmage-Mendelsohn triangularization of a radioactive decay chain's bipartite graph in the rapid computation of its pseudospectra, its exponentiation, and the numerical solution of its Bateman system of depletion equations are briefly discussed