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
Computing Maximum C-planar Subgraphs
No full textDeciding c-planarity for a given clustered graph C = (G, T ) is one of the most challenging problems in current graph drawing research. Though it is yet unknown if this problem is solvable in polynomial time, latest research focused on algorithmic approaches for special classes of clustered graphs. In this paper, we introduce an approach to solve the general problem using integer linear programming (ILP) techniques. We give an ILP formulation that also includes the natural generalization of cplanarity testing—the maximum c-planar subgraph problem —and solve this ILP with a branch-and-cut algorithm. Our computational results show that this approach is already successful for many clustered graphs of small to medium sizes and thus can be the foundation of a practically efficient algorithm that integrates further sophisticated ILP techniques
Cyclic Leveling of Directed Graphs
No full textThe Sugiyama framework is the most commonly used concept for visualizing directed graphs.It draws them in a hierarchical way and operates in four phases: cycle removal, leveling, crossing reduction, and coordinate assignment. However, there are situations where cycles must be displayed as such, e.g., distinguished cycles in the biosciences and processes that repeat in a daily or weekly turn. This forbids the removal of cycles. In their seminal paper Sugiyama et al. also introduced recurrent hierarchies as a concept to draw graphs with cycles. However, this concept has not received much attention since then.
In this paper we investigate the leveling problem for cyclic graphs. We show that minimizing the sum of the length of all edges is NP-hard for a given number of levels and present three different heuristics for the leveling problem. This sharply contrasts the situation in the hierarchical style of drawing directed graphs, where this problem is solvable in polynomial time
Non-Convex Representations of Graphs
No full textWe show that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are non-convex polygon
Subdivision Drawings of Hypergraphs
No full textWe introduce the concept of subdivision drawings of hypergraphs. In a subdivision drawing each vertex corresponds uniquely to a face of a planar subdivision and, for each hyperedge, the union of the faces corresponding to the vertices incident to that hyperedge is connected. Vertex-based Venn diagrams and concrete Euler diagrams are both subdivision drawings. In this paper we study two new types of subdivision drawings which are more general than concrete Euler diagrams and more restricted than vertex-based Venn diagrams. They allow us to draw more hypergraphs than the former while having better aesthetic properties than the latter
Visual Specification of Layout
No full textWe give an overview of a drawing approach that combines the concepts constraint satisfaction, attribute evaluation and transformation. The approach is tailored to an editor for visual languages, which supports structured editing as well as free-hand editing. In this paper, we focus on the visual specification of such a layout algorithm. As a running example, deterministic finite automata are used
Constrained Point-Set Embeddability of Planar Graphs
No full textThis paper starts the investigation of a constrained version of the pointset embeddability problem. Let G = (V , E ) be a planar graph with n vertices, G′ = (V ′ , E ′ ) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: (i) If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E \ E ′ have at most 4 bends each. (ii) If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E \ E ′ is at most 8. (iii) If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E \ E ′ is O(2k )
Minimum Segment Drawings of Series-Parallel Graphs with the Maximum Degree Three
No full textA minimum segment drawing Γ of a planar graph G is a straight line drawing of G that has the minimum number of segments among all straight line drawings of G. In this paper, we give a linear-time algorithm for computing a minimum segment drawing of a series-parallel graph with the maximum degree three.To the best of our knowledge, this is the first algorithm for computing minimum segment drawings of an important subclass of planar graphs
Approximating the Crossing Number of Apex Graphs
No full textWe show that the crossing number of an apex graph, i.e. a graph G from which only one vertex v has to be removed to make it planar, can be approximated up to a factor of
∆(G − v ) · d(v )/2 by solving the vertex inserting problem, i.e. inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Due to a recently developed polynomial algorithm for the latter problem, this establishes the first polynomial fixed-constant approximation algorithm for the crossing number problem of apex graphs with bounded degree