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
Graph Drawing in the Cloud: Privately Visualizing Relational Data Using Small Working Storage
No full textWe study graph drawing in a cloud-computing context where data is stored externally and processed using a small local working storage. We show that a number of classic graph drawing algorithms can be efficiently implemented in such a framework where the client can maintain privacy while constructing a drawing of her graph
Planar Lombardi Drawings for Subcubic Graphs
No full textWe prove that every planar graph with maximum degree three has a planar drawing in which the edges are drawn as circular arcs that meet at equal angles around every vertex. Our construction is based on the Koebe–Andreev–Thurston circle packing theorem, and uses a novel type of Voronoi diagram for circle packings that is invariant under Möbius transformations, defined using three-dimensional hyperbolic geometry. We also use circle packing to construct planar Lombardi drawings of a special class of 4-regular planar graphs, the medial graphs of polyhedral graphs, and we show that not every 4-regular planar graph has a planar Lombardi drawing. We have implemented our algorithm for 3-connected planar cubic graphs
Point-Set Embeddability of 2-Colored Trees
No full textIn this paper we study bichromatic point-set embeddings of 2-colored trees on 2-colored point sets, i.e., point-set embeddings of trees (whose vertices are colored red and blue) on point sets (whose points are colored red and blue) such that each red (blue) vertex is mapped to a red (resp. blue) point. We prove that deciding whether a given 2-colored tree admits a bichromatic point-set embedding on a given convex point set is an -complete problem; we also show that the same problem is linear-time solvable if the convex point set does not contain two consecutive points with the same color. Furthermore, we prove a 3n/2 − O(1) lower bound and a 2n upper bound (a 7n/6 − O(logn) lower bound and a 4n/3 upper bound) on the minimum size of a universal point set for straight-line bichromatic embeddings of 2-colored trees (resp. 2-colored binary trees). Finally, we show that universal convex point sets with n points exist for 1-bend bichromatic point-set embeddings of 2-colored trees
Extending Partial Representations of Circle Graphs
No full textThe partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some pre-drawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire G, i.e., whether one can draw the remaining chords into a partially pre-drawn representation.
Our main result is a polynomial-time algorithm for partial representation extension of circle graphs. To show this, we describe the structure of all representation a circle graph based on split decomposition. This can be of an independent interest
The Visible Perimeter of an Arrangement of Disks
No full textGiven a collection of n opaque unit disks in the plane, we want to find a stacking order for them that maximizes their visible perimeter, the total length of all pieces of their boundaries visible from above. We prove that if the centers of the disks form a dense point set, i.e., the ratio of their maximum to their minimum distance is , then there is a stacking order for which the visible perimeter is . We also show that this bound cannot be improved in the case of the piece of a sufficiently small square grid. On the other hand, if the set of centers is dense and the maximum distance between them is small, then the visible perimeter is with respect to any stacking order. This latter bound cannot be improved either. These results partially answer some questions of Cabello, Haverkort, van Kreveld, and Speckmann
On the Upward Planarity of Mixed Plane Graphs
No full textA mixed plane graph is a plane graph whose edge set is partitioned into a set of directed edges and a set of undirected edges. An orientation of a mixed plane graph G is an assignment of directions to the undirected edges of G resulting in a directed plane graph TeX . In this paper, we study the computational complexity of testing whether a given mixed plane graph G is upward planar, i.e., whether it admits an orientation resulting in a directed plane graph G such that G admits a planar drawing in which each edge is represented by a curve monotonically increasing in the y-direction according to its orientation.
Our contribution is threefold. First, we show that the upward planarity testing problem is solvable in cubic time for mixed outerplane graphs. Second, we show that the problem of testing the upward planarity of mixed plane graphs reduces in quadratic time to the problem of testing the upward planarity of mixed plane triangulations. Third, we exhibit linear-time testing algorithms for two classes of mixed plane triangulations, namely mixed plane 3-trees and mixed plane triangulations in which the undirected edges induce a forest
Strip Planarity Testing
No full textIn this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph G(V,E) and a function γ:V → {1,2,…,k} and asks whether a planar drawing of G exists such that each edge is monotone in the y-direction and, for any u,v ∈ V with γ(u) < γ(v), it holds y(u) < y(v). The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity, upward planarity, and level planarity. We show that the problem is polynomial-time solvable if G has a fixed planar embedding
Stub Bundling and Confluent Spirals for Geographic Networks
No full textEdge bundling is a technique to reduce clutter by routing parts of several edges along a shared path. In particular, it is used for visualization of geographic networks where vertices have fixed coordinates. Two main drawbacks of the common approach of bundling the interior of edges are that (i) tangents at endpoints deviate from the line connecting the two endpoints in an uncontrolled way and (ii) there is ambiguity as to which pairs of vertices are actually connected. Both severely reduce the interpretability of geographic network visualizations.
We therefore propose methods that bundle edges at their ends rather than their interior. This way, tangents at vertices point in the general direction of all neighbors of edges in the bundle, and ambiguity is avoided altogether. For undirected graphs our approach yields curves with no more than one turning point. For directed graphs we introduce a new drawing style, confluent spiral drawings, in which the direction of edges can be inferred from monotonically increasing curvature along each spiral segment
Drawing Arrangement Graphs in Small Grids, or How to Play Planarity
No full textWe describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area O(n 7/6). No known input causes our algorithm to use area Ω(n 1 + ε ) for any ε > 0; finding such an input would represent significant progress on the famous k-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the Planarity puzzle