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
Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph
No full textGiven a graph G and a subset F ⊆ E(G) of its edges, is there a drawing of G in which all edges of F are free of crossings? We show that this question can be solved in polynomial time using a Hanani-Tutte style approach. If we require the drawing of G to be straight-line, but allow up to one crossing along each edge in F, the problem turns out to be as hard as the existential theory of the real numbers
Bitonic st-orderings of Biconnected Planar Graphs
No full textVertex orderings play an important role in the design of graph drawing algorithms. Compared to canonical orderings, st-orderings lack a certain property that is required by many drawing methods. In this paper, we propose a new type of st-ordering for biconnected planar graphs that relates the ordering to the embedding. We describe a linear-time algorithm to obtain such an ordering and demonstrate its capabilities with two applications
A Crossing Lemma for the Pair-Crossing Number
No full textThe pair-crossing number of a graph G, pcr(G), is the minimum possible number of pairs of edges that cross each other (possibly several times) in a drawing of G. It is known that there is a constant c ≥ 1/64 such that for every (not too sparse) graph G with n vertices and m edges pcr(G)≥c(m^3/n^2) . This bound is tight, up to the constant c. Here we show that c ≥ 1/34.2 if G is drawn without adjacent crossings
Morphing Schnyder Drawings of Planar Triangulations
No full textWe consider the problem of morphing between two planar drawings of the same triangulated graph, maintaining straight-line planarity. A paper in SODA 2013 gave a morph that consists of O(n 2) steps where each step is a linear morph that moves each of the n vertices in a straight line at uniform speed [1]. However, their method imitates edge contractions so the grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes. Using Schnyder embeddings, we are able to morph in O(n 2) linear morphing steps and improve the grid size to O(n)×O(n) for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. The morphs are visually attractive. Our method involves implementing the basic “flip” operations of Schnyder woods as linear morphs
Increasing-Chord Graphs On Point Sets
No full textWe tackle the problem of constructing increasing-chord graphs spanning point sets. We prove that, for every point set P with n points, there exists an increasing-chord planar graph with O(n) Steiner points spanning P. Further, we prove that, for every convex point set P with n points, there exists an increasing-chord graph with O(n logn) edges (and with no Steiner points) spanning P
Planar and Quasi Planar Simultaneous Geometric Embedding
No full textA simultaneous geometric embedding (SGE) of two planar graphs G 1 and G 2 with the same vertex set is a pair of straight-line planar drawings Γ1 of G 1 and Γ2 of G 2 such that each vertex is drawn at the same point in Γ1 and Γ2. Many papers have been devoted to the study of which pairs of graphs admit a SGE, and both positive and negative results have been proved. We extend the study of SGE, by introducing and characterizing a new class of planar graphs that makes it possible to immediately extend several positive results that rely on the property of strictly monotone paths. Moreover, we introduce a relaxation of the SGE setting where Γ1 and Γ2 are required to be quasi planar (i.e., they can have crossings provided that there are no three mutually crossing edges). This relaxation allows for the simultaneous embedding of pairs of planar graphs that are not simultaneously embeddable in the classical SGE setting and opens up to several new interesting research questions
Luatodonotes: Boundary Labeling for Annotations in Texts
No full textWe present a tool for annotating Latex documents with comments. Our annotations are placed in the left, right, or both margins, and connected to the corresponding positions in the text with arrows (so-called leaders). Problems of this type have been studied under the name boundary labeling. We consider various leader types (straight-line, rectilinear, and Bézier) and modify existing algorithms to allow for annotations of varying height. We have implemented our algorithms in Lua; they are available for download as an easy-to-use Luatex package
Height-Preserving Transformations of Planar Graph Drawings
No full textThere are numerous styles of planar graph drawings, such as straight-line drawings, poly-line drawings, orthogonal graph drawings and visibility representations. Given a planar drawing in one of these styles, can it be converted it to another style while keeping the height unchanged? This paper answers this question for (nearly) all pairs of these styles, as well as for related styles that additionally restrict edges to be y-monotone and/or vertices to be horizontal line segments. These transformations can be used to develop new graph drawing results, especially for height-optimal drawings
Advances on Testing C-Planarity of Embedded Flat Clustered Graphs
No full textWe show a polynomial-time algorithm for testing c-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face
3D Graph Visualization with the Oculus Rift
No full textVisualization of large graphs in 3D has been hampered by the expense and inconvenience of a virtual reality equipment. The Oculus Rift is an affordable head-mounted VR system that is becoming popular in gaming and education markets. The Gluskap software package for creating and editing graphs in 3D has been extended to include support for the Oculus Rift for stereographic 3D viewing, and navigation