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
Maximizing the Degree of (Geometric) Thickness-t Regular Graphs
No full textIn this paper, we show that there exist (6t−1)-regular graphs with thickness t, by constructing such an example graph. Since all graphs of thickness t must have at least one node with degree less than 6t, this construction is optimal. We also show, by construction, that there exist 5t-regular graphs with geometric thickness at most t. Our construction for the latter builds off of a relationship between geometric thickness and the Cartesian product of two graphs
2-Layer Fan-Planarity: From Caterpillar to Stegosaurus
No full textIn a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are assigned to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs
On Embeddability of Buses in Point Sets
No full textSet membership of points in the plane can be visualized by connecting corresponding points via graphical features, like paths, trees, polygons, ellipses. In this paper we study the bus embeddability problem (BEP): given a set of colored points we ask whether there exists a planar realization with one horizontal straight-line segment per color, called bus, such that all points with the same color are connected with vertical line segments to their bus. We present an ILP and an FPT algorithm for the general problem. For restricted versions of this problem, such as when the relative order of buses is predefined, or when a bus must be placed above all its points, we provide efficient algorithms. We show that another restricted version of the problem can be solved using 2-stack pushall sorting. On the negative side we prove the NP-completeness of a special case of BEP
Gestalt Principles in Graph Drawing
No full textGestalt principles are rules for the organization of perceptual scenes. They were introduced in the context of philosophy and psychology in the 19th century and were used to define principles of human perception in the early 20th century. The Gestalt (form, in German) principles include, among others: proximity, the grouping of closely positioned objects; similarity, the grouping of objects of similar shape or color; continuation, the grouping of objects that form a continuous pattern; and symmetry, the grouping of objects that form symmetric patterns. Gestalt principles have been extensively applied in user interface design, graphic design, and information visualization
Representing Directed Trees as Straight Skeletons
No full textThe straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process.
In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed
Graduate Workshop Recent Trends in Graph Drawing: Curves, Graphs, and Intersections
No full textThe Organizing Committee of GD 2015 hosted a gradate workshop, continuing the tradition of previous Symposia, focusing on open problems in graph drawing
SVEN: An Alternative Storyline Framework for Dynamic Graph Visualization
No full textThe world is a dynamic place, so when we use graphs to help understand real world problems the structure of such graphs inevitably changes over time. Understanding this change is important, but often challenging. Techniques for general purpose dynamic graph visualizations generally fall into one of two broad categories: animation or timeline based techniques [2]. Simple approaches using animation or small multiples experience challenges with change blindness and “preserving the user’s mental map” [1]. Storyline visualization techniques [5, 7] hold promise, though these techniques were not originally designed as general purpose solutions for dynamic graph visualization
Knuthian Drawings of Series-Parallel Flowcharts
No full textIn 1963, Knuth published the first paper on a computer algorithm for a graph drawing problem, entitled “Computer-drawn Flowcharts” [8]. In this paper, Knuth describes an algorithm that takes as input an n-vertex directed graph G that represents a flowchart and, using the modern language of graph drawing, produces an orthogonal drawing of G
An Incremental Layout Method for Visualizing Online Dynamic Graphs
No full textGraphs provide a visual means for examining relation data and force-directed methods are often used to lay out graphs for viewing. Making sense of a dynamic graph as it evolves over time is challenging, and previous force-directed methods were designed for static graphs. In this paper, we present an incremental version of a multilevel multi-pole layout method with a refinement scheme incorporated, which enables us to visualize online dynamic networks while maintaining a mental map of the graph structure. We demonstrate the effectiveness of our method and compare it to previous methods using several network data sets