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
Experimental Analysis of the Accessibility of Drawings with Few Segments
No full textThe visual complexity of a graph drawing is defined as the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges, e.g., one needs only one line segment to draw two collinear incident edges. We study the question if drawings with few segments have a better aesthetic appeal and help the user to asses the underlying graph. We design an experiment that investigates two different graph types (trees and sparse graphs), three different layout algorithms for trees, and two different layout algorithms for sparse graphs. We asked the users to give an aesthetic ranking on the layouts and to perform a furthest-pair or shortest-path task on the drawings
Lombardi Drawings of Knots and Links
No full textKnot and link diagrams are projections of one or more 3-dimensional simple closed curves into lR2, such that no more than two points project to the same point in lR2. These diagrams are drawings of 4-regular plane multigraphs. Knots are typically smooth curves in lR3, so their projections should be smooth curves in lR2 with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defined by circular-arc edges and perfect angular resolution).
We show that several knots do not allow plane Lombardi drawings. On the other hand, we identify a large class of 4-regular plane multigraphs that do have Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a plane 2-Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is near-Lombardi, that is, it can be drawn as Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset ε, while maintaining a 180∘ angle between opposite edges
Revisited Experimental Comparison of Node-Link and Matrix Representations.
No full textVisualizing network data is applicable in domains such as biology, engineering, and social sciences. We report the results of a study comparing the effectiveness of the two primary techniques for showing network data: node-link diagrams and adjacency matrices. Specifically, an evaluation with a large number of online participants revealed statistically significant differences between the two visualizations. Our work adds to existing research in several ways. First, we explore a broad spectrum of network tasks, many of which had not been previously evaluated. Second, our study uses a large dataset, typical of many real-life networks not explored by previous studies. Third, we leverage crowdsourcing to evaluate many tasks with many participants
Drawing Dynamic Graphs Without Timeslices.
No full textTimeslices are often used to draw and visualize dynamic graphs. While timeslices are a natural way to think about dynamic graphs, they are routinely imposed on continuous data. Often, it is unclear how many timeslices to select: too few timeslices can miss temporal features such as causality or even graph structure while too many timeslices slows the drawing computation. We present a model for dynamic graphs which is not based on timeslices, and a dynamic graph drawing algorithm, DynNoSlice, to draw graphs in this model. In our evaluation, we demonstrate the advantages of this approach over timeslicing on continuous data sets
Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count.
No full textWe show that triangle-free penny graphs have degeneracy at most two, list coloring number (choosability) at most three, diameter D=Ω(n‾√), and at most min(2n−Ω(n‾√),2n−D−2)edges
Gap-Planar Graphs.
No full textWe introduce the family of k-gap-planar graphs for k≥0, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition finds motivation in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs
Beyond Outerplanarity
No full textWe study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., convex drawings. We consider two families of graph classes with nice convex drawings: outer k-planar graphs, where each edge is crossed by at most k other edges; and, outer k-quasi-planar graphs where no k edges can mutually cross.
We show that the outer k-planar graphs are (⌊4k+1‾‾‾‾‾‾√⌋+1)
-degenerate, and consequently that every outer k-planar graph can be (⌊4k+1‾‾‾‾‾‾√⌋+2)-colored, and this bound is tight. We further show that every outer k-planar graph has a balanced separator of size at most 2k+3
. For each fixed k, these small balanced separators allow us to test outer k-planarity in quasi-polynomial time, i.e., none of these recognition problems are NP-hard unless ETH fails.
For the outer k-quasi-planar graphs we discuss the edge-maximal graphs which have been considered previously under different names. We also construct planar 3-trees that are not outer 3-quasi-planar.
Finally, we restrict outer k-planar and outer k-quasi-planar drawings to closed drawings, where the vertex sequence on the boundary is a cycle in the graph. For each k, we express closed outer k-planarity and closed outer k-quasi-planarity in extended monadic second-order logic. Thus, since outer k-planar graphs have bounded treewidth, closed outer k-planarity is linear-time testable by Courcelle’s Theorem
Visual Similarity Perception of Directed Acyclic Graphs: A Study on Influencing Factors
No full textWhile visual comparison of directed acyclic graphs (DAGs) is commonly encountered in various disciplines (e.g., finance, biology), knowledge about humans’ perception of graph similarity is currently quite limited. By graph similarity perception we mean how humans perceive commonalities and differences in graphs and herewith come to a similarity judgment. As a step toward filling this gap the study reported in this paper strives to identify factors which influence the similarity perception of DAGs. In particular, we conducted a card-sorting study employing a qualitative and quantitative analysis approach to identify (1) groups of DAGs that are perceived as similar by the participants and (2) the reasons behind their choice of groups. Our results suggest that similarity is mainly influenced by the number of levels, the number of nodes on a level, and the overall shape of the graph