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
Simultaneous Embeddings with Few Bends and Crossings
No full textA simultaneous embedding with fixed edges (Sefe) of two planar graphs R and B is a pair of plane drawings of R and B that coincide when restricted to their common vertices and edges. We show that whenever R and B admit a Sefe, they also admit a Sefe in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if R and B are trees then one bend per edge and four crossings per edge pair suffice, (2) if R is a planar graph and B is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if R and B are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. This improves on results by Grilli et al. (GD’14), who prove that nine bends per edge suffice, and by Chan et al. (GD’14), who prove that twenty-four crossings per edge pair suffice
Rook-Drawing for Plane Graphs
No full textMotivated by visualization of large graphs, we introduce a new type of graph drawing called “rook-drawing”. A rook-drawing of a graph G is obtained by placing the n nodes of G on the intersections of a regular grid, such that each row and column of the grid supports exactly one node. This paper focuses on rook-drawings of planar graphs. We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs. We then characterize the maximal planar graphs admitting a planar straight-line rook-drawing, which are unique for a given order. Finally, we give a linear time algorithm to compute a polyline planar rook-drawing for plane graphs with at most n−3 bent edges
Shape-Based Quality Metrics for Large Graph Visualization
No full textWe propose a new family of quality metrics for graph drawing; in particular, we concentrate on larger graphs. We illustrate these metrics with examples and apply the metrics to data from previous experiments, leading to the suggestion that the new metrics are effective
Drawing Graphs Using Body Gestures
No full textWe introduce a new gesture-based user interface for drawing graphs that recognizes specific body gestures using the Microsoft Kinect sensor. Our preliminary user study demonstrates the potential for using gesture-based interfaces in graph drawing
The Degenerate Crossing Number and Higher-Genus Embeddings
No full textIf a graph embeds in a surface with k crosscaps, does it always have an embedding in the same surface in which every edge passes through each crosscap at most once? This well-known open problem can be restated using crossing numbers: the degenerate crossing number, dcr(G), of G equals the smallest number k so that G has an embedding in a surface with k crosscaps in which every edge passes through each crosscap at most once. The genus crossing number, gcr(G), of G equals the smallest number k so that G has an embedding in a surface with k crosscaps. The question then becomes whether dcr(G) = gcr(G), and it is in this form that it was first asked by Mohar.
We show that dcr(G) ≤ 6 gcr(G), and dcr(G) = gcr(G) as long as dcr(G) ≤ 3. We can separate dcr and gcr for (single-vertex) graphs with embedding schemes, but it is not clear whether the separating example can be extended into separations on simple graphs. Finally, we show that if a graph can be embedded in a surface with crosscaps, then it has an embedding in that surface in which every edge passes through each crosscap at most twice. This implies that dcr is NP-complete
Drawing Graphs with Vertices and Edges in Convex Position
No full textA graph has strong convex dimension 2, if it admits a straight-line drawing in the plane such that its vertices are in convex position and the midpoints of its edges are also in convex position. Halman, Onn, and Rothblum conjectured that graphs of strong convex dimension 2 are planar and therefore have at most 3n−6 edges. We prove that all such graphs have at most 2n−3 edges while on the other hand we present a class of non-planar graphs of strong convex dimension 2. We also give lower bounds on the maximum number of edges a graph of strong convex dimension 2 can have and discuss variants of this graph class. We apply our results to questions about large convexly independent sets in Minkowski sums of planar point sets, that have been of interest in recent years
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
No full textWhen can a plane graph with prescribed edge lengths and prescribed angles (from among {0,180°, 360°}) be folded flat to lie in an infinitesimally thick line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such flat-foldable plane graphs by two obviously necessary but also sufficient conditions, proving a conjecture made in 2001: the angles at each vertex should sum to 360°, and every face of the graph must itself be flat foldable. This characterization leads to a linear-time algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles, and a polynomial-time algorithm for counting the number of distinct folded states
Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition
No full textThe force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs as they compute a quadratic number of forces in each iteration. We speed up this computation by using an approximation based on the well-separated pair decomposition.
We perform experiments on a large number of graphs and show that we can strongly reduce the runtime—even on graphs with less then a hundred vertices—without a significant influence on the quality of the drawings (in terms of number of crossings and deviation in edge lengths)
Hanani-Tutte for Radial Planarity
No full textA drawing of a graph G is radial if the vertices of G are placed on concentric circles C1,…,Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling.
We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth