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
Angle and Distance Constraints on Tree Drawings
No full textWe consider planar drawings of trees that must satisfy constraints
on the angles between edges incident to a common vertex and on the
distances between adjacent vertices. These requirements arise naturally
in many applications such as drawing phylogenetic trees or route maps.
For straight-line drawings, either class of constraints is always
realizable, whereas their combination is not in general. We show that
straight-line realizability can be tested in linear time, and give an
algorithm that produces drawing satisfying both groups of constraints
together in a model where edges are represented as polylines with at
most two bends per edge or as continuously differentiable curves
Simultaneous Graph Embedding with Bends and Circular Arcs
No full textWe consider the problem of simultaneous embedding of planar graphs. We demonstrate how
to simultaneously embed a path and an n-level planar graph and how to use radial
embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph.
We also show how to use star-shaped levels to find 2-bends per path edge
simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms
run in O(n) time
Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps
No full textIn this paper we consider a new problem that occurs when drawing
wiring diagrams or public transportation networks. Given an
embedded graph G=(V,E) (e.g., the streets served by a bus network)
and a set L of paths in G (e.g., the bus lines), we want to draw
the paths along the edges of G such that they cross each other as
few times as possible. For esthetic reasons we insist that the
relative order of the paths that traverse a node does not change
within the area occupied by that node.
Our main contribution is an algorithm that minimizes the number of
crossings on a single edge {u,v} in E if we are given the order
of the incoming and outgoing paths. The difficulty is deciding the
order of the paths that terminate in u or v with respect to the
fixed order of the paths that do not end there. Our algorithm uses
dynamic programming and takes O(n^2) time, where n is the number
of terminating paths
Partitions of Graphs into Trees
No full textIn this paper, we study the k-tree partition problem which is a
partition of the set of edges of a graph into k edge-disjoint trees.
This problem occurs at several places with applications e.g. in network
reliability and graph theory. In graph drawing there is the still
unbeaten (n-2) x (n-2) area planar straight line drawing of maximal
planar graphs using Schnyder's realizers [15]}, which are a
3-tree partition of the inner edges. Maximal planar bipartite graphs
have a 2-tree partition, as shown by Ringel [14].
Here we give a different proof of this result with a linear time
algorithm. The algorithm makes use of a new ordering which is of interest
of its own. Then we establish the NP-hardness of the k-tree partition
problem for general graphs and k >= 2. This parallels NP-hard partition
problems for the vertices [3], but it
contrasts the efficient computation of partitions into forests (also known
as arboricity) by matroid techniques [7]
On representations by contact and intersection of segments
No full textA necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a contact family of segments and points. We deduce that any 4-connected 3-colorable plane graph is the contact graph of a family of segments and that any 4-colored planar graph without an induced C4 using 4 colors is the intersection graph of a family of straight line segments
Three Dimensional Drawings of Bounded Degree Trees
No full textWe show an algorithm for constructing 3D straight-line drawings of balanced constant degree trees. The drawings have linear volume
and optimal aspect ratio. As a side effect, we also give an algorithm for constructing 2D drawings of balanced constant degree trees in linear area, with optimal aspect ratio and with better angular resolution with respect to the one of [8]. Further, we present an algorithm for constructing 3D poly-line drawings of trees whose degree is bounded by n^{1/3} in linear volume and with optimal aspect ratio
Embedding Graphs Simultaneously with Fixed Edges
No full textWe show that a planar graph and a tree can always be simultaneously embedded with fixed edges and that two outerplanar graphs generally cannot
How Important is the "Mental Map"? -- an Empirical Investigation of a Dynamic Graph Layout Algorithm
No full textWhile some research has been performed on the human understanding of static graph layout algorithms, dynamic graph layout algorithms have only recently been developed sufficiently to enable similar investigations. This paper presents the first empirical analysis of a dynamic graph layout
algorithm, focusing on the assumption that maintaining the "mental map" between time-slices assists with the
comprehension of the evolving graph. The results confirm this assumption with respect to some categories of tasks
Morphing Planar Graphs in Spherical Space
No full textWe consider the problem of intersection-free planar graph morphing,
and in particular, a generalization from Euclidean space to spherical
space. We show that there exists a continuous and intersection-free
morph between two sphere drawings of a maximally planar graph,
provided that both sphere drawings have convex inscribed polytopes,
where sphere drawings are the spherical equivalent of plane drawings:
intersection-free geodesic-arc drawings. In addition, we describe a
morphing algorithm along with its implementation. Movies of sample
morphs can be found at http://www.cs.arizona.edu/~mlandis/smorph
Characterization of Unlabeled Level Planar (ULP) Trees
No full textConsider a graph G drawn in the plane so that each vertex
lies on a distinct horizontal line \ell_j = \{(x, j) \,|\, x \in \BB{R}\}. The bijection
that maps the set of n vertices V to a set of distinct horizontal lines \isTR{ for
forms a labeling of the vertices. Such a graph G with the labeling
is called an n-level graph and is said to be n-level planar if it can
be drawn with straight-line edges and no crossings while keeping each
vertex on its own level. In this paper, we consider the class of trees that
are n-level planar regardless of their labeling. We call such trees unlabeled
level planar (ULP). Our contributions are three-fold. First, we provide a
complete characterization of ULP trees in terms of a pair of forbidden
subtrees. Second, we show how to draw ULP trees in linear time. Third,
we provide a linear time recognition algorithm for ULP trees.