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
Clustered Planarity: Small Clusters in Eulerian Graphs
No full textWe present several polynomial-time algorithms for c-planarity testing for clustered graphs with clusters of size at most three. The most general result concerns a special class of Eulerian graphs, namely graphs obtained from a fixed-size 3-connected graph by multiplying and then subdividing edges. We further give algorithms for 3-connected graphs, and for graphs with small faces. The last result applies with no restrictions on the cluster size
Cyclic Level Planarity Testing and Embedding
No full textIn this paper we introduce cyclic level planar graphs, which are a planar version of the recurrent hierarchies from Sugiyama et al. [8] and the cyclic extension of level planar graphs, where the first level is the successor of the last level. We study the testing and embedding problem and solve it for strongly connected graphs in time
Cover Contact Graphs
No full textWe study problems that arise in the context of covering certain geometric objects (so-called , e.g., points or disks) by a set of other geometric objects (a so-called , e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pairwise disjoint, but they can touch. We call the contact graph of a cover a (CCG). We are interested in two types of tasks: (a) deciding whether a given seed set has a connected CCG, and (b) deciding whether a given graph has a realization as a CCG on a given seed set. Concerning task (a) we give efficient algorithms for the case that seeds are points and covers are disks or triangles. We show that the problem becomes NP-hard if seeds and covers are disks. Concerning task (b) we show that it is even NP-hard for point seeds and disk covers (given a fixed correspondence between vertices and seeds)
Matched Drawings of Planar Graphs
No full textA natural way to draw two planar graphs whose vertex sets are matched is to assign each matched pair a unique y-coordinate. In this paper we introduce the concept of such matched drawings, which are a relaxation of simultaneous geometric embeddings with mapping. We study which classes of graphs allow matched drawings and show that (i) two 3-connected planar graphs or a 3-connected planar graph and a tree may not be matched drawable, while (ii) two trees or a planar graph and a planar graph of some special families-such as unlabeled level planar (ULP) graphs or the family of "carousel graphs"-are always matched drawable
Algorithms for Multi-Criteria One-Sided Boundary Labeling
No full textWe present new algorithms for labeling a set of points in the plane with labels that are aligned to the left of the bounding box of . The points are connected to their labels by curves (leaders) that consist of two segments: a horizontal segment, and a second segment at a fixed angle with the first. Our algorithm finds a collection of non-intersecting leaders that minimizes the total number of bends, the total length, or any other 'badness' function of the leaders. An experimental evaluation of the performance is included
Constrained Simultaneous and Near-Simultaneous Embeddings
No full textA geometric simultaneous embedding of two graphs G_1=(V_1,E_1) and G_2=(V_2,E_2) with a bijective mapping of their vertex sets gamma : V_1 rightarrow V_2 is a pair of planar straight-line drawings Gamma _1 of G_1 and Gamma _2 of G_2, such that each vertex v_2=gamma(v_1) is mapped in Gamma _2 to the same point where v_1 is mapped in Gamma _1, where v_1 in V_1 and v_2 in V_2.
In this paper we examine several constrained versions and a relaxed version of the geometric simultaneous embedding problem. We show that if the input graphs are assumed to share no common edges this does not seem to yield large classes of graphs that can be simultaneously embedded. Further, if a prescribed combinatorial embedding for each input graph must be preserved, then we can answer some of the problems that are still open for geometric simultaneous embedding. Finally, we present some positive and negative results on the near-simultaneous embedding problem, in which vertices are not mapped exactly to the same but to "near" points in the different drawings
Straight-Line Orthogonal Drawings of Binary and Ternary Trees
No full textIn this paper we provide upper and lower bounds on the area requirement of straight-line orthogonal drawings of -node binary and ternary trees. Namely, we show algorithms for constructing order-preserving straight-line orthogonal drawings of binary trees in area, straight-line orthogonal drawings of ternary trees in area, and straight-line orthogonal drawings of complete ternary trees in area. As far as we know, the ones we present are the first algorithms achieving sub-quadratic area for these problems. Further, for upward order-preserving straight-line orthogonal drawings of binary trees and for order-preserving straight-line orthogonal drawings of ternary trees we provide area lower bounds, that we also prove to be tight
Efficient Extraction of Multiple Kuratowski Subdivisions
No full textA graph is planar if and only if it does not contain a Kuratowski subdivision. Hence such a subdivision can be used as a witness for non-planarity. Modern planarity testing algorithms allow to extract a single such witness in linear time. We present the first linear time algorithm which is able to extract multiple Kuratowski subdivisions at once. This is of particular interest for, e.g., Branch-and-Cut algorithms which require multiple such subdivisions to generate cut constraints. The algorithm is not only described theoretically,
but we also present an experimental study of its implementation
Moving Vertices to Make Drawings Plane
No full textIn John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. In this paper we investigate the related problem MinMovedVertices which asks for the minimum number of vertex moves. First, we show that MinMovedVertices is NP-hard and hard to approximate. Second, we establish a connection to the graph-drawing problem 1BendPointSetEmbeddability, which yields similar results for that problem. Third, we give bounds for the behavior of MinMovedVertices on trees and general planar graphs
Representation of Planar Hypergraphs by Contacts of Triangles
No full textMany representation theorems extend from planar graphs to planar hypergraphs. The authors proved in [10] that every planar graph has a representation by contact of triangles. We prove here that this representation result extend to planar linear hypergraphs. Although the graph proof was simple and led to a linear time drawing algorithm, the extension for hypergraphs needs more work. The proof we give here relies on a combinatorial characterization of those hypergraphs which are representable by contact of segments in the plane, We propose some possible generalization directions and open problems, related to the order dimension of the incidence posets of hypergraphs