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 Upward Drawings of Trees on a Given Grid
No full textComputing a minimum-area planar straight-line drawing of a graph is known to be NP-hard for planar graphs, even when restricted to outerplanar graphs. However, the complexity question is open for trees. Only a few hardness results are known for straight-line drawings of trees under various restrictions such as edge length or slope constraints. On the other hand, there exist polynomial-time algorithms for computing minimum-width (resp., minimum-height) upward drawings of trees, where the height (resp., width) is unbounded.
In this paper we take a major step in understanding the complexity of the area minimization problem for strictly-upward drawings of trees, which is one of the most common styles for drawing rooted trees. We prove that given a rooted tree T and a W×H
grid, it is NP-hard to decide whether T admits a strictly-upward (unordered) drawing in the given grid. The hardness result holds both in polyline and straight-line drawing settings
Non-crossing Paths with Geographic Constraints
No full textA geographic network is a graph whose vertices are restricted to lie in a prescribed region in the plane. In this paper we begin to study the following fundamental problem for geographic networks: can a given geographic network be drawn without crossings? We focus on the seemingly simple setting where each region is a unit length vertical segment, and one wants to connect pairs of segments with a path that lies inside the convex hull of the two segments. We prove that when paths must be drawn as straight line segments, it is NP-complete to determine if a crossing-free solution exists. In contrast, we show that when paths must be monotone curves, the question can be answered in polynomial time. In the more general case of paths that can have any shape, we show that the problem is polynomial under certain assumptions
Graph Drawing Contest Report.
No full textThis report describes the 24th Annual Graph Drawing Contest, held in conjunction with the 25th International Symposium on Graph Drawing (GD’17) in Boston, United States of America. The purpose of the contest is to monitor and challenge the current state of the art in graph-drawing technology
Which Graph Layout Gives a Good Shape for Large Graphs?
No full textThis poster empirically investigates the quality of large graph layouts using shape-based quality metrics. We present our preliminary results on several real-world graphs
Simple Compact Monotone Tree Drawings.
No full textA monotone drawing of a graph G is a straight-line drawing of G such that every pair of vertices is connected by a path that is monotone with respect to some direction.
Trees, as a special class of graphs, have been the focus of several papers and, recently, He and He [6] showed how to produce a monotone drawing of an arbitrary n-vertex tree that is contained in a 12n×12n
grid.
In this paper, we present a simple algorithm that constructs for each arbitrary tree a monotone drawing on a grid of size at most n×n
On Vertex and Empty-ply Proximity Drawings
No full textWe initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equal to half the length of the longest edge incident to the vertex. The vertex-ply of a drawing is determined by the vertex covered by the maximum number of disks. The main motivation for considering this relaxation is to relate the concept of ply to proximity drawings. In fact, if we interpret the set of disks as proximity regions, a drawing with vertex-ply number 1 can be seen as a weak proximity drawing, which we call empty-ply drawing. We show non-trivial relationships between the ply number and the vertex-ply number. Then, we focus on empty-ply drawings, proving some properties and studying what classes of graphs admit such drawings. Finally, we prove a lower bound on the ply and the vertex-ply of planar drawings
EPG-representations with Small Grid-Size
No full textIn an EPG-representation of a graph G, each vertex is represented by a path in the rectangular grid, and (v, w) is an edge in G if and only if the paths representing v an w share a grid-edge. Requiring paths representing edges to be x-monotone or, even stronger, both x- and y-monotone gives rise to three natural variants of EPG-representations, one where edges have no monotonicity requirements and two with the aforementioned monotonicity requirements. The focus of this paper is understanding how small a grid can be achieved for such EPG-representations with respect to various graph parameters.
We show that there are m-edge graphs that require a grid of area Ω(m)
in any variant of EPG-representations. Similarly there are pathwidth-k graphs that require height Ω(k) and area Ω(kn) in any variant of EPG-representations. We prove a matching upper bound of O(kn) area for all pathwidth-k graphs in the strongest model, the one where edges are required to be both x- and y-monotone. Thus in this strongest model, the result implies, for example, O(n), O(nlogn) and O(n^3/2) area bounds for bounded pathwidth graphs, bounded treewidth graphs and all classes of graphs that exclude a fixed minor, respectively. For the model with no restrictions on the monotonicity of the edges, stronger results can be achieved for some graph classes, for example an O(n) area bound for bounded treewidth graphs and O(nlog^2 n) bound for graphs of bounded genus
MLSEB: Edge Bundling Using Moving Least Squares Approximation
No full textEdge bundling methods can effectively alleviate visual clutter and reveal high-level graph structures in large graph visualization. Researchers have devoted significant efforts to improve edge bundling according to different metrics. As the edge bundling family evolve rapidly, the quality of edge bundles receives increasing attention in the literature accordingly. In this paper, we present MLSEB, a novel method to generate edge bundles based on moving least squares (MLS) approximation. In comparison with previous edge bundling methods, we argue that our MLSEB approach can generate better results based on a quantitative metric of quality, and also ensure scalability and the efficiency for visualizing large graphs
C-Planarity of Embedded Cyclic c-Graphs
No full textWe show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle