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
Characterization of Unlabeled Level Planar Graphs
No full textWe present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of n vertices, for any of the n! possible mappings. These graphs are equivalent to the set of unlabeled level planar (ULP) graphs that are level planar over all possible labelings. Our contributions are twofold. First, we provide linear time drawing algorithms for ULP graphs. Second, we provide a complete characterization of ULP graphs by showing that any other graph must contain a subgraph homeomorphic to one of seven forbidden graphs
Minimizing the Area for Planar Straight-Line Grid Drawings
No full textStraight-line grid drawings of bounded size is a classical topic in graph drawing. The Graph Drawing Challenge 2006 dealt with minimizing the area of planar straight-line grid drawings. In this paper, we show that it is NP-complete to decide if a planar graph has a planar straight-line drawing on a grid of given size. Furthermore, we present a new iterative approach to compactify planar straight-line grid drawings. In an experimental study, we evaluate the quality of the compactified drawings with respect to the size of the area as well as to other measures
On Planar Polyline Drawings
No full textWe present a linear time algorithm that produces a planar polyline drawing for a plane graph with vertices in a grid of size bounded by , where . It uses at most bends, and each edge uses at most one bend. Compared with the area optimal polyline drawing algorithm in [3], our algorithm uses a larger grid size bound in trade for a smaller bound on the total number of bends. Their bend bound is . Our algorithm is based on a transformation from Schnyder's realizers [6, 7] of maximal plane graphs to transversal structures [4, 5] for maximal internally 4-connected plane graphs. This transformation reveals important relations between the two combinatorial structures for plane graphs, which is of independent interest
Constrained Stress Majorization Using Diagonally Scaled Gradient Projection
No full textConstrained stress majorization is a promising new technique for integrating application
specific layout constraints into force-directed graph layout. We significantly improve the speed and convergence properties of the constrained stress-majorization technique for graph layout by employing a diagonal scaling of the stress function. Diagonal scaling requires the active-set quadratic programming solver used in the projection step to be extended to handle separation constraints with scaled variables, i.e. of the form s_i y_i + g_ij le s_j y_j. The changes, although relatively small, are quite subtle and explained in detail
Large-Scale Graphics: Digital Nature and Laser Projection
No full textIn this talk, I will sketch out two challenging research topics by showing computer generated visual materials. One is raster-graphics technologies on how to represent large-scale natural sceneries, and the other is laser projection technologies enabling us to display large-scale vector graphics. The former topic includes the modeling and rendering techniques having the both abilities of LOD (Level-Of-Detail) and anti-aliasing indispensable for efficiently and effectively representing large-scale scenes including a huge amount of fine objects like botanical trees, and the efficient real-time animation techniques implemented by utilizing 1/f-noise for defeating the computational time required for strict physically-based simulation. The latter topic is the exploratory research on laser projection where there is almost no researcher yet. Laser graphics has strong relation to pen and ink illustration in the field of NPR (Non-Photorealistic-Rendering) and might be usable to represent Graph Drawing
Point-Set Embedding of Trees with Edge Constraints
No full textGiven a graph G with n vertices and a set S of n points in the plane, a point-set embedding$ of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph G' subset G on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of G'. We concentrate on trees and show how to compute the output in O(n^2 log n) time and with at most 1 + 2 lceil k/2 rceil bends per edge, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least k-3 bends for some of the edges
The Complexity of Several Realizability Problems for Abstract Topological Graphs
No full textAn (briefly an ) is a pair where is a graph and is a set of pairs of its edges. An AT-graph is if can be drawn in the plane in such a way that each pair of edges from crosses exactly once and no other pair crosses. We present a polynomial algorithm which decides whether a given complete AT-graph is simply realizable. On the other hand, we show that other similar realizability problems for (complete) AT-graphs are NP-hard
Colorability in Orthogonal Graph Drawing
No full textThis paper studies the question: What is the maximum integer k_b,n such that every k_b,n-colorable graph has a b-bend n-dimensional orthogonal box drawing?
We give an exact answer for the orthogonal line drawing in all dimensions and for the 3-dimensional rectangle visibility representation. We present an upper and lower bound for the 3-dimensional orthogonal drawing by rectangles and general boxes. Particularly, we improve the best known upper bound for the 3-dimensional orthogonal box drawing from 183 to 42 and the lower bound from 3 to 22
A Bipartite Strengthening of the Crossing Lemma
No full textThe celebrated Crossing Lemma states that, in every drawing of a graph with n vertices and m geq 4n edges there are at least Omega(m^3/n^2) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m^2/n^2) other edges. We strengthen the Crossing Lemma for drawings in which any two edges cross in at most O(1) points.
We prove for every k N mathbb N that every graph G with n vertices and m geq 3n edges drawn in the plane such that any two edges intersect in at most k points has two disjoint subsets of edges, E_1 and E_2, each of size at least c_km^2/n^2, such that every edge in E_1 crosses all edges in E_2, where c_k>0 only depends on k. This bound is best possible up to the constant c_k for every . We also prove that every graph G with n vertices and edges drawn in the plane with -monotone edges has disjoint subsets of edges, E_1 and E_2, each of size Omega(m^2/ (n^2 , rm polylog , n))E_1E_2E_1$ and E_2 have size O(m^2/(n^2 log (m/n)))
LunarVis - Analytic Visualizations of Large Graphs
No full textThe analysis and the exploration of complex networks nowadays involves the identification of a multitude of analytic properties that have been ascertained to constitute crucial characteristics of networks. We propose a new layout paradigm for drawing large networks, with a focus on decompositional properties. The visualization is based on the general shape of an annulus and supports the immediate recognition of a large number of abstract features of the decomposition while drawing all elements. Our layouts offer remarkable readability of the decompositional connectivity and are capable of revealing subtle structural traits