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 Embeddability of Two Partitions
No full textWe study the simultaneous embeddability of a pair of partitions of the same underlying set into disjoint blocks. Each element of the set is mapped to a point in the plane and each block of either of the two partitions is mapped to a region that contains exactly those points that belong to the elements in the block and that is bounded by a simple closed curve. We establish three main classes of simultaneous embeddability (weak, strong, and full embeddability) that differ by increasingly strict well-formedness conditions on how different block regions are allowed to intersect. We show that these simultaneous embeddability classes are closely related to different planarity concepts of hypergraphs. For each embeddability class we give a full characterization. We show that (i) every pair of partitions has a weak simultaneous embedding, (ii) it is NP-complete to decide the existence of a strong simultaneous embedding, and (iii) the existence of a full simultaneous embedding can be tested in linear time
Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
No full textWe investigate crossing minimization for 1-page and 2-page book drawings. We show that computing the 1-page crossing number is fixed-parameter tractable with respect to the number of crossings, that testing 2-page planarity is fixed-parameter tractable with respect to treewidth, and that computing the 2-page crossing number is fixed-parameter tractable with respect to the sum of the number of crossings and the treewidth of the input graph. We prove these results via Courcelle’s theorem on the fixed-parameter tractability of properties expressible in monadic second order logic for graphs of bounded treewidth
Column Planarity and Partial Simultaneous Geometric Embedding
No full textWe introduce the notion of column planarity of a subset R of the vertices of a graph G. Informally, we say that R is column planar in G if we can assign x-coordinates to the vertices in R such that any assignment of y-coordinates to them produces a partial embedding that can be completed to a plane straight-line drawing of G. Column planarity is both a relaxation and a strengthening of unlabeled level planarity. We prove near tight bounds for column planar subsets of trees: any tree on n vertices contains a column planar set of size at least 14n/17 and for any ε > 0 and any sufficiently large n, there exists an n-vertex tree in which every column planar subset has size at most (5/6 + ε)n.
We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partial SGE (PSGE). A PSGE of two graphs G 1 and G 2 allows some of their vertices to map to two different points in the plane. We show how to use column planar subsets to construct k-PSGEs in which k vertices are still mapped to the same point. In particular, we show that any two trees on n vertices admit an 11n/17-PSGE, two outerpaths admit an n/4-PSGE, and an outerpath and a tree admit a 11n/34-PSGE
GION: Interactively Untangling Large Graphs on Wall-Sized Displays
No full textData sets of very large graphs are now commonplace; the scale of these graphs presents considerable difficulties for graph visualization methods. The use of interactive techniques and large screens have been proposed as two possible avenues to address these difficulties.This paper presents GION, a new skeletal animation technique for interacting with large graphs on wall-sized displays. Our technique is based on a physical simulation, and aims to enhance the users’ ability to efficiently interact with the graph visualization for exploratory analysis. We conducted a user study to evaluate our technique against standard operations available in most graph layout editors, and the study shows that the new technique produces layouts with less stress, and fewer edge crossings. GION is preferred by users, and requires significantly less mouse movement
Are Crossings Important for Drawing Large Graphs?
No full textReducing the number of edge crossings is considered one of the most important graph drawing aesthetics. While real-world graphs tend to be large and dense, most of the earlier work on evaluating the impact of edge crossings utilizes relatively small graphs that are manually generated and manipulated. We study the effect on task performance of increased edge crossings in automatically generated layouts for graphs, from different datasets, with different sizes, and with different densities. The results indicate that increasing the number of crossings negatively impacts accuracy and performance time and that impact is significant for small graphs but not significant for large graphs. We also quantitatively evaluate the impact of edge crossings on crossing angles and stress in automatically constructed graph layouts. We find a moderate correlation between minimizing stress and the minimizing the number of crossings
Drawing Partially Embedded and Simultaneously Planar Graphs
No full textWe investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph (PEG) problem—to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph—and the simultaneous planarity (SEFE) problem—to find planar drawings of two graphs that coincide on shared vertices and edges. In both cases we show that if the required planar drawings exist, then there are planar drawings with a linear number of bends per edge and, in the case of simultaneous planarity, a constant number of crossings between every pair of edges. Our proofs provide efficient algorithms if the combinatorial embedding information about the drawing is given. Our result on partially embedded graph drawing generalizes a classic result of Pach and Wenger showing that any planar graph can be drawn with fixed locations for its vertices and with a linear number of bends per edge
Unit Contact Representations of Grid Subgraphs with Regular Polytopes in 2D and 3D
No full textWe present a strategy to construct unit proper contact representations (UPCR) for subgraphs of certain highly symmetric grids. This strategy can be applied to obtain graphs admitting UPCRs with squares and cubes, whose recognition is NP-complete.
We show that subgraphs of the square grid allow for UPCR with squares which strengthens the previously known cube representation. Indeed, we give UPCR for subgraphs of a d-dimensional grid with d-cubes. Additionally, we show that subgraphs of the triangular grid admit a UPCR with cubes, implying that the same holds for each subgraph of an Archimedean grid. Considering further polygons, we construct UPCR with regular 3k-gons of the hexagonal grid and UPCR with regular 4k-gons of the square grid
The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
No full textMany well-known graph drawing techniques, including force directed drawings, spectral graph layouts, multidimensional scaling, and circle packings, have algebraic formulations. However, practical methods for producing such drawings ubiquitously use iterative numerical approximations rather than constructing and then solving algebraic expressions representing their exact solutions. To explain this phenomenon, we use Galois theory to show that many variants of these problems have solutions that cannot be expressed by nested radicals or nested roots of low-degree polynomials. Hence, such solutions cannot be computed exactly even in extended computational models that include such operations
On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs
No full textAn st-path in a drawing of a graph is self-approaching if during a traversal of the corresponding curve from s to any point t′ on the curve the distance to t′ is non-increasing. A path has increasing chords if it is self-approaching in both directions. A drawing is self-approaching (increasing-chord) if any pair of vertices is connected by a self-approaching (increasing-chord) path.
We study self-approaching and increasing-chord drawings of triangulations and 3-connected planar graphs. We show that in the Euclidean plane, triangulations admit increasing-chord drawings, and for planar 3-trees we can ensure planarity. Moreover, we give a binary cactus that does not admit a self-approaching drawing. Finally, we show that 3-connected planar graphs admit increasing-chord drawings in the hyperbolic plane and characterize the trees that admit such drawings
Planar Induced Subgraphs of Sparse Graphs
No full textWe show that every graph has an induced pseudoforest of at least n − m/4.5 vertices, an induced partial 2-tree of at least n − m/5 vertices, and an induced planar subgraph of at least n − m/5.2174 vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs. We also show that the size of the largest K h -minor-free graph in a given graph can sometimes be at most n − m/6 + o(m)