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
A Ramsey-Type Result for Geometric ℓ-Hypergraphs
No full textLet n ≥ ℓ ≥ 2 and q ≥ 2. We consider the minimum N such that whenever we have N points in the plane in general position and the ℓ-subsets of these points are colored with q colors, there is a subset S of n points all of whose ℓ-subsets have the same color and furthermore S is in convex position. This combines two classical areas of intense study over the last 75 years: the Ramsey problem for hypergraphs and the Erdős-Szekeres theorem on convex configurations in the plane. For the special case ℓ = 2, we establish a single exponential bound on the minimum N such that every complete N-vertex geometric graph whose edges are colored with q colors, yields a monochromatic convex geometric graph on n vertices.
For fixed ℓ ≥ 2 and q ≥ 4, our results determine the correct exponential tower growth rate for N as a function of n, similar to the usual hypergraph Ramsey problem, even though we require our monochromatic set to be in convex position. Our results also apply to the case of ℓ = 3 and q = 2 by using a geometric variation of the Stepping-up lemma of Erdős and Hajnal. This is in contrast to the fact that the upper and lower bounds for the usual 3-uniform hypergraph Ramsey problem for two colors differ by one exponential in the tower
Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
No full textWe consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an O(n√logn) approximation for paths and matchings, and an O(n) approximation for general graphs
Ravenbrook Chart: A New Library for Graph Layout and Visualization
No full textRavenbrook Chart is a newly-available library which implements layout and interactive display of large, complex graphs. It provides spring-embedded, layered and circular layouts. It has been deployed in mature applications and free web service uses it to visualise graphs. It is now available free of charge as a permissively licensed library
Testing Planarity by Switching Trains
No full textWe show that planarity testing can be interpreted as a train switching problem. Train switching problems have been studied in the context of permutation networks, i. e., permuting the cars of a train on a given railroad network [5]. The cars enter the network one at a time, some are stored temporarily in the network and the cars leave the network in the prescribed permutation. For the planarity test we use the metaphor of train switching in the context of graph layouts. In a graph layout the vertices are processed according to a total order, i. e., an ordering of the vertices, which is called linear layout. The edges are data items that are inserted to and removed from a given data structure. The vertices are processed in the order of the linear layout. At each vertex, at first all edges incident to preceding vertices are removed from the data structure and then all edges incident to succeeding vertices are inserted into the data structure. These operations must obey the principles of the underlying data structure, such as “LIFO” for a stack or “FIFO” for a queue. A graph G is a stack graph, i. e., has a stack layout, if and only if it is outerplanar, and it is a 2-stack graph if and only if it is a subgraph of a planar graph with a Hamiltonian cycle [3]
Achieving Good Angular Resolution in 3D Arc Diagrams
No full textWe study a three-dimensional analogue to the well-known graph visualization approach known as arc diagrams. We provide several algorithms that achieve good angular resolution for 3D arc diagrams, even for cases when the arcs must project to a given 2D straight-line drawing of the input graph. Our methods make use of various graph coloring algorithms, including an algorithm for a new coloring problem, which we call localized edge coloring
Exploiting Air-Pressure to Map Floorplans on Point Sets
No full textWe prove a conjecture of Ackerman, Barequet and Pinter. Every floorplan with n segments can be embedded on every set of n points in generic position. The construction makes use of area universal floorplans also known as area universal rectangular layouts.
The notion of area used in our context depends on a nonuniform density function. We, therefore, have to generalize the theory of area universal floorplans to this situation. The method is then used to prove a result about accommodating points in floorplans that is slightly more general than the conjecture of Ackerman et al
Sketched Graph Drawing: A Lesson in Empirical Studies
No full textThis paper reports on a series of three similar graph drawing empirical studies, and describes the results of investigating subtle variations on the experimental method. Its purpose is two-fold: to report the results of the experiments, as well as to illustrate how easy it is to inadvertently make conclusions that may not stand up to scrutiny. While the results of the initial experiment were validated, instances of speculative conclusions and inherent bias were identified. This research highlights the importance of stating the limitations of any experiment, being clear about conclusions that are speculative, and not assuming that (even minor) experimental decisions will not affect the results
COAST: A Convex Optimization Approach to Stress-Based Embedding
No full textVisualizing graphs using virtual physical models is probably the most heavily used technique for drawing graphs in practice. There are many algorithms that are efficient and produce high-quality layouts. If one requires that the layout also respect a given set of non-uniform edge lengths, however, force-based approaches become problematic while energy-based layouts become intractable. In this paper, we propose a reformulation of the stress function into a two-part convex objective function to which we can apply semi-definite programming (SDP). We avoid the high computational cost associated with SDP by a novel, compact re-parameterization of the objective function using the eigenvectors of the graph Laplacian. This sparse representation makes our approach scalable. We provide experimental results to show that this method scales well and produces reasonable layouts while dealing with the edge length constraints
