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
k-colored point-set embeddability of outerplanar graphs
No full textThis paper addresses the problem of designing drawing algorithms that receive as input a planar graph G, a partitioning of the vertices of G into k different semantic categories V_0,\cdots, V_{k-1}, and k disjoint sets S_0, \cdots, S_{k-1} of points in the plane with |V_i|=|S_i| (i \in \{0, \cdots, k-1\}).The desired output is a planar drawing such that the
vertices of V_i are mapped onto the points of S_i and such that the curve complexity of the edges (i.e. the number of bends along each edge) is kept small. Particular attention is devoted to outerplanar graphs, for which lower and upper bounds on the number of bends in the drawings are established
Integrating Edge Routing into Force-Directed Layout
No full textThe typical use of force-directed layout is to create organic-looking,
straight-edge drawings of large graphs while combinatorial techniques are
generally preferred for high-quality layout of small to medium sized graphs.
In this paper we integrate edge-routing techniques into a force-directed layout
method based on constrained stress majorisation. Our basic procedure takes an
initial layout for the graph, including poly-line paths for the edges, and
improves this layout by moving the nodes to reduce stress and moving edge bend
points to straighten the edges and reduce their overall length. Separation
constraints between nodes and edge bend points are used to ensure that nodes
do not overlap edges or other nodes and that no additional edge
crossings are introduced
Multipole-Based Force Approximation Revisited - a Simple but Fast Implementation Using a Dynamized Enclosing-Circle-Enhanced k-d-Tree
No full textMost force-directed graph drawing algorithms depend for speed
crucially on efficient methods for approximating repulsive forces between a
large number of particles.
A combination of various tree data structures and multi-pole approximations
has been successfully used by a number of authors.
If a multi-level approach is taken, in the late (and due to the large number
of particles computationally intensive) steps, movements of particles are quite limited.
We utilize this fact by basing force-calculations on an easy updatable tree
data structure.
Using explicit distance checks instead of relying on implicit guarantees
provided by quadtrees and avoiding local expansions of the multi-pole
expansion leads to a very simple implementation that is faster than
comparable earlier methods.
The latter claim is supported by experimental results
SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding
No full textWe present a fast spectral graph drawing algorithm for drawing
undirected connected graphs. Classical Multi-Dimensional Scaling
yields a quadratic-time spectral algorithm, which approximates the
real distances of the nodes in the final drawing with their graph
theoretical distances. We build from this idea to develop the
linear-time spectral graph drawing algorithm SSDE. We reduce the
space and time complexity of the spectral decomposition by
approximating the distance matrix with the product of three
smaller matrices, which are formed by sampling rows and columns of
the distance matrix. The main advantages of our algorithm are that
it is very fast and it gives aesthetically pleasing results, when
compared to other spectral graph drawing algorithms. The runtime
for typical 10^5 node graphs is about one second and for 10^6
node graphs about ten seconds
Trees with Convex Faces and Optimal Angles
No full textWe consider drawings of trees in which all edges incident to leaves can be extended to infinite rays without crossing, partitioning the plane into infinite convex polygons. Among all such drawings we seek the one maximizing the angular resolution of the drawing. We find linear time algorithms for solving this problem, both for plane trees and for trees without a fixed embedding. In any such drawing, the edge lengths may be set independently of the angles, without crossing; we describe multiple strategies for setting these lengths
Schematisation of Tree Drawings
No full textGiven a tree T spanning a set of points S in the plane, we
study the problem of drawing T using only line segments aligned
with a fixed set of directions C. The vertices in the drawing
must lie within a given distance r of each original point p in S,
and an objective function counting the number of bends must be
minimised. We propose five versions of this problem using different
objective functions, and algorithms to solve them. This work has
potential applications in geographic map schematisation and metro
map layout
Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs
No full textA straight-line drawing of a plane graph
is called an open rectangle-of-influence drawing if there is no vertex
in the proper inside of the axis-parallel rectangle defined by the two ends of every edge.
In an inner triangulated plane graph,
every inner face is a triangle although the outer face is not always a triangle. In this paper,
we first obtain a sufficient condition for an inner triangulated plane graph G
to have an open rectangle-of-influence drawing;
the condition is expressed in terms of a labeling of angles of a subgraph of G.
We then present an O(n^{1.5}/log n)-time algorithm to examine whether G satisfies
the condition and, if so, construct an open rectangle-of-influence drawing of G on an
(n-1) x (n-1) integer grid, where n is the number of vertices in G
Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
No full textTree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by
allowing an arbitrary planar graph to index the decomposition. We prove that every graph that excludes a fixed graph as a minor has a planar decomposition with
bounded width and a linear number of bags.
The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. We prove that planar decompositions are intimately related to the crossing number, in the sense that a graph with bounded degree has linear crossing number if and only if it has a planar decomposition with bounded width and linear order. It follows from the above result about planar decompositions that every graph with bounded degree and an excluded minor has linear crossing number.
Analogous results are proved for the convex and rectilinear crossing numbers. In particular, every graph with bounded degree and bounded tree-width has linear convex crossing number, and every K_3,3-minor-free graph with bounded degree has linear rectilinear crossing number
Computing Geometric Minimum-Dilation Graphs is NP-Hard
No full textConsider a geometric graph G, drawn with straight lines in the plane. For every pair a,b of vertices of G, we compare the shortest-path
distance between a and b in G (with Euclidean edge lengths) to their actual Euclidean distance in the plane. The worst-case ratio of these two values, for all pairs of vertices, is called the vertex-to-vertex dilation of G.
We prove that computing a minimum-dilation graph that connects a given n-point set in the plane, using not more than a given number m of edges, is an NP-hard
problem, no matter if edge crossings are allowed or forbidden. In addition, we show that the minimum dilation tree over a given point set may in fact contain
edge crossings
Chordal Graphs as Intersection Graphs of Pseudosegments
No full textWe investigate which chordal graphs have a representation as intersection graphs of pseudosegments. The main contribution is a
construction which shows that all chordal graphs which have a representation as intersection graph of subpaths on a tree are
representable. A family of intersection graphs of substars of a star is used to show that not all chordal graphs are representable by
pseudosegments