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
Upright-Quad Drawing of st-Planar Learning Spaces
No full textWe consider graph drawing algorithms for learning spaces, a type of -oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any st-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an st-planar learning space.
We also describe connections between these graphs and arrangements of translates of a quadrant
Biclique Edge Cover Graphs and Confluent Drawings
No full textConfluent drawing is a technique that allows some non-planar
graphs to be visualized in a planar way. This approach merges
edges together, drawing groups of them as single tracks,
similar to train tracks. In the general case, producing confluent
drawings automatically has proven quite difficult. We introduce
the biclique edge cover graph that represents a graph G as an
interconnected set of cliques and bicliques. We do this in such a
way as to permit a straightforward transformation to a confluent
drawing of G. Our result is a new sufficient condition for
confluent planarity and an additional algorithmic approach for
generating confluent drawings. We give some experimental results
gauging the performance of existing confluent drawing heuristics
Graph-Drawing Contest Report
No full textThis report describes the Thirteenth Annual Graph Drawing Contest, held
in conjunction with the 2006 Graph Drawing Symposium in Karlsruhe,
Germany.
The purpose of the contest is to monitor and challenge the
current state of the graph-drawing technology
Straight-line drawing of quadrangulations
No full textThis article introduces a straight-line drawing algorithm for
quadrangulations, in the family of the face-counting algorithms. It
outputs in linear time a drawing on a regular W x H grid such that
W+H=n-1-Delta, where n is the number of vertices and Delta is
an explicit combinatorial parameter of the quadrangulation
Smoother transitions between breadth-first-spanning-tree-based drawings
No full textWe demonstrate a collection of techniques that seek to make the transition between drawings based on
two topologically distinct spanning trees of the same graph as clear as possible
Stretching of Jordan arc contact systems
No full textUsing a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least 3 free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible
Rectangular Layouts and Contact Graphs
No full textContact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding {\em rectangular layouts} is a key problem. We study the area-optimization problem and show that it is NP-hard to find a
minimum-area rectangular layout of a given contact graph. We present -time algorithms that construct O(n^2)-area rectangular layouts
for general contact graphs and O(n\log n)-area rectangular layouts for trees. (For trees, this is an O(\log n)-approximation algorithm.) We also present an infinite family of graphs (rsp., trees) that require \Omega(n^2) (rsp., \Omega(n\log n)) area. We derive these result by presenting a new characterization of graphs that admit rectangular layouts using the related concept of {\em rectangular duals}. A corollary to our results relates the class of graphs that admit rectangular layouts to rectangle of influence drawings
Schnyder Woods and Orthogonal Surfaces
No full textIn this paper we study connections between Schnyder woods and
orthogonal surfaces. Schnyder woods and the face counting approach
have important applications in graph drawing and dimension
theory. Orthogonal surfaces explain the connections between these
seemingly unrelated notions. We use these connections for an intuitive
proof of the Brightwell-Trotter Theorem which says that the face lattice of a
3-polytope minus one face has dimension three. Our proof yields a
companion linear time algorithm for the construction of the three
linear orders that realize the face lattice.
Coplanar orthogonal surfaces are in correspondance with a large class
of convex straight line drawings of 3-connected planar graphs. We show
that Schnyder's face counting approach with weighted faces can be used
to construct all coplanar orthogonal surfaces and hence the
corresponding drawings. Appropriate weights are computable in linear
time
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
A New Approximation Algorithm for Bend Minimization in the Kandinsky Model
No full textThe Kandinsky model has been introduced by Fössmeier and Kaufmann in order to deal with planar orthogonal drawings of planar graphs with maximal vertex
degree higher than four [7]. No polynomial-time algorithm is known for computing a (region preserving) bend minimal Kandinsky drawing. In this paper we suggest a new 2-approximation algorithm for this problem. Our extensive computational experiments [13] show that the quality of the computed solutions is better than those of its predecessors [6]. E.g., for all instances in
the Rome graph benchmark library [4] it computed the optimal solution, and for randomly generated triangulated graphs with up to 800 vertices, the absolute error was less than 2 on average