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
Interactive Network Exploration to Derive Insights: Filtering, Clustering, Grouping, and Simplification
No full textThe growing importance of network analysis has increased attention on interactive exploration to derive insights and support personal, business, legal, scientific, or national security decisions. Since networks are often complex and cluttered, strategies for effective filtering, clustering, grouping, and simplification are helpful in finding key nodes and links, surprising clusters, important groups, or meaningful patterns. We describe readability metrics and strategies that have been implemented in NodeXL, our free and open source network analysis tool, and show examples from our research. While filtering, clustering, and grouping have been used in many tools, we present several advances on these techniques. We also discuss our recent work on motif simplification, in which common patterns are replaced with compact and meaningful glyphs, thereby improving readability
Graph Drawing by Classical Multidimensional Scaling: New Perspectives
No full textWith shortest-path distances as input, classical multidimensional scaling can be regarded as a spectral graph drawing algorithm, and recent approximation techniques make it scale to very large graphs. In comparison with other methods, however, it is considered inflexible and prone to degenerate layouts for some classes of graphs.
We want to challenge this belief by demonstrating that the method can be flexibly adapted to provide focus+context layouts. Moreover, we propose an alternative instantiation that appears to be more suitable for graph drawing and prevents certain degeneracies
Grid Drawings and the Chromatic Number
No full textA grid drawing of a graph maps vertices to the grid and edges to line segments that avoid grid points representing other vertices. We show that a graph G is -colorable, , if and only if there is a grid drawing of G in in which no line segment intersects more than q grid points. This strengthens the result of D. Flores Pen̋aloza and F. J. Zaragoza Martinez. Second, we study grid drawings with a bounded number of columns, introducing some new NP-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by D. Flores Pen̋aloza and F. J. Zaragoza Martinez
Tangles and Degenerate Tangles
No full textWe study some variants of Conway’s thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a degenerate tangle. We settle a problem of Pach, Radoičić, and Tóth [7], by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles
Force-Directed Graph Drawing Using Social Gravity and Scaling
No full textForce-directed layout algorithms produce graph drawings by resolving a system of emulated physical forces. We present techniques for using social gravity as an additional force in force-directed layouts, together with a scaling technique, to produce drawings of trees and forests, as well as more complex social networks. Social gravity assigns mass to vertices in proportion to their network centrality, which allows vertices that are more graph-theoretically central to be visualized in physically central locations. Scaling varies the gravitational force throughout the simulation, and reduces crossings relative to unscaled gravity. In addition to providing this algorithmic framework, we apply our algorithms to social networks produced by Mark Lombardi, and we show how social gravity can be incorporated into force-directed Lombardi-style drawings
On the Faithfulness of Graph Visualizations
No full textIntroduction.
Graph drawing algorithms developed over the past 30 years aim to produce “readable” pictures of graphs. Here “readability” is measured by aesthetic criteria, such as few crossings or few edge bends or small grid drawing area. However, the readability criteria for visualizing graphs, though necessary, are not sufficient for effective graph visualization.
This poster introduces another kind of criterion, generically called “faithfulness”. Intuitively, a graph drawing algorithm is “faithful” if it maps different graphs to distinct drawings. Faithfulness criteria are especially relevant for modern methods that handle very large and complex graphs; data reduction or aggregation or generalisation are commonly exercised to enhance readability
More Graph Drawing in the Cloud: Data-Oblivious st-Numbering, Visibility Representations, and Orthogonal Drawing of Biconnected Planar Graphs
No full textWe give a new efficient data-oblivious PRAM simulation and several new data-oblivious graph-drawing algorithms with application to privacy-preserving graph-drawing in a cloud computing context
Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
No full textA graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1-planar graphs do not admit straight-line drawings. We show that every 3-connected 1-planar graph has a straight-line drawing on an integer grid of quadratic size, with the exception of a single edge on the outer face that has one bend. The drawing can be computed in linear time from any given 1-planar embedding of the graph
On Balanced -Contact Representations
No full textIn a -contact representation of a planar graph G, each vertex is represented as an axis-aligned plus shape consisting of two intersecting line segments (or equivalently, four axis-aligned line segments that share a common endpoint), and two plus shapes touch if and only if their corresponding vertices are adjacent in G. Let the four line segments of a plus shape be its arms. In a c-balanced representation, c ≤ 1, every arm can touch at most ⌈cΔ⌉ other arms, where Δ is the maximum degree of G. The widely studied T- and L-contact representations are c-balanced representations, where c could be as large as 1. In contrast, the goal in a c-balanced representation is to minimize c. Let c k , where k ∈ {2,3}, be the smallest c such that every planar k-tree has a c-balanced representation. In this paper we show that 1/4 ≤ c 2 ≤ 1/3 ( = b 2) and 1/3 < c 3 ≤ 1/2 ( = b 3). Our result has several consequences. Firstly, planar k-trees admit 1-bend box-orthogonal drawings with boxes of size ⌈bkΔ⌉×⌈bkΔ⌉ , which generalizes a result of Tayu, Nomura, and Ueno. Secondly, they admit 1-bend polyline drawings with 2⌈bkΔ⌉ slopes, which is significantly smaller than the 2Δ upper bound established by Keszegh, Pach, and Pálvölgyi for arbitrary planar graphs
