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
On Embedding a Cycle in a Plane Graph
No full textConsider a planar drawing Gamma of a planar graph G such that the vertices are drawn as small circles and the edges are drawn as thin strips. Consider a cycle c of G. Is it possible to draw c as a non-intersecting closed curve inside Gamma, following the circles that correspond in Gamma to the vertices of c and the strips that connect them? We show that this test can be done in polynomial time and study this problem in the framework of clustered planarity for highly non-connected clustered graphs
Bar k-Visibility Graphs: Bounds on the Number of Edges, Chromatic Number, and Thickness
No full textLet S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility representation, if there exists a one-to-one correspondence between vertices of G and bars in S, such that there is an edge between two vertices in G if and only if there exists an unobstructed vertical line of sight between their corresponding bars. If bars are allowed to see through each other, the graphs representable in this way are precisely the interval graphs. We consider representations in which bars are allowed to see through at most k other bars. Since all bar visibility graphs are planar, we seek measurements of closeness to planarity for bar k-visibility graphs. We obtain an upper bound on the number of edges in a bar k-visibility graph. As a consequence, we obtain an upper bound of 12 on the chromatic number of bar 1-visibility graphs, and a tight upper bound of 8 on the size of the largest complete bar 1-visibility graph. We conjecture that bar 1-visibility graphs have thickness at most 2
Crossing number of toroidal graphs
No full textIt is shown that if a graph of n vertices can be drawn on the torus without edge crossings and the maximum degree of its vertices is at most d, then its planar crossing number cannot exceed c_dn, where c_d is a constant depending only on d. This bound, conjectured by Brass, cannot be improved, apart from the value of the constant. We strengthen and generalize this result to the case when the graph has a crossing-free drawing on an orientable surface of higher genus and there is no restriction on the degrees of the vertices
On Extending a Partial Straight-Line Drawing
No full textWe investigate the computational complexity of the following problem. Given a planar graph in which some vertices have already been placed in the plane, place the remaining vertices to form a planar straight-line drawing of the whole graph. We show that this extensibility problem, proposed in the 2003 "Selected Open Problems in Graph Drawing", is NP-complete
Small Area Drawings of Outerplanar Graphs
No full textWe show three linear time algorithms for constructing planar straight-line grid drawings of outerplanar graphs. The first and the second algorithm are for balanced outerplanar graphs. Both require linear area. The drawings produced by the first algorithm are not outerplanar while those produced by the second algorithm are. On the other hand, the first algorithm constructs drawings with better angular resolution. The third algorithm constructs outerplanar drawings of general outerplanar graphs with O(n^{1.48}) area. Further, we study the interplay between the area requirements of the drawings of an outerplanar graph and the area requirements of a special class of drawings of its dual tree
An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs
No full textIn the last decade several algorithms that generate straight-line drawings of general large graphs have been invented.In this paper we investigate some of these methods that are based on force-directed or algebraic approaches in terms of running time and drawing quality on a big variety of artificial and real-world graphs. Our experiments indicate that there exist significant differences in drawing qualities and running times depending on the classe
s of tested graphs and algorithms
Proper and Planar Drawings of Graphs on Three Layers
No full textA proper k-layer planar graph, for an integer k>=0, is any graph with a planar drawing in which the vertices are drawn on k horizontal lines called layers and each edge is drawn a straight-line segment between end-vertices on adjacent layers. In this paper, we point out errors in an algorithm of Foessmeier and Kaufmann (CIAC, 1997) for recognizing proper 3-layer planar graphs, and then present a new characterization of proper 3-layer planar graphs that is partially based on their algorithm. Using the characterization, we then derive corresponding linear-time algorithms for recognizing and drawing proper 3-layer planar graphs. On the basis of our results, we predict that the approach of Foessmeier and Kaufmann will not easily generalize for drawings on four or more layers and suggest another possible approach along with some of the reasons why it may be more successful
Upward Spirality and Upward Planarity Testing
No full textLet G be a digraph whose SPQR-tree does not have any R-node. The main result of this paper is a polynomial-time algorithm that tests whether G is upward planar and, if so, returns an upward planar representation of G. As an application of this result, a new FPT algorithm is presented that solves the upward planarity testing problem for general digraphs. Our results use the new notion of upward spirality that, informally speaking, is a measure of the "level of winding" that a triconnected component of G can have in an upward pla
nar representation of G
On edges crossing few other edges in simple topological complete graphs
No full textWe study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A {em topological graph} T=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersetion point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is {em simple}, if any two edges meet in at most one common point. Let h=h(n) be the smallest integer such that every simple complete topological graph on n vertices contains an edge crossing at most h other edges. We show that Omega(n^{3/2})le h(n) le O(n^2/log^{1/4}n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn^2
WhatsOnWeb: Using Graph Drawing to Search the Web
No full textOne of the most challenging issues in mining information from the World Wide Web is the design of systems that can present the data to the end user by clustering them into meaningful semantic categories. We envision that the analysis of the results of a Web search can significantly take advantage of advanced graph drawing techniques. In this paper we strengthen our point by describing the visual functionalities of WhatsOnWeb. WhatsOnWeb is a meta search clustering engine explicitly designed to make it possible that the user browses the Web by means of drawings of graphs whose nodes represent clusters of coherent data and whose edges describe semantic relationships between pairs of clusters. A prototype of WhatsOnWeb is available at http://whatsonweb.diei.unipg.it/