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
Evaluation of Two Interaction Techniques for Visualization of Dynamic Graphs
No full textSeveral techniques for visualization of dynamic graphs are based on different spatial arrangements of a temporal sequence of node-link diagrams. Many studies in the literature have investigated the importance of maintaining the user’s mental map across this temporal sequence, but usually each layout is considered as a static graph drawing and the effect of user interaction is disregarded. We conducted a task-based controlled experiment to assess the effectiveness of two basic interaction techniques: the adjustment of the layout stability and the highlighting of adjacent nodes and edges. We found that generally both interaction techniques increase accuracy, sometimes at the cost of longer completion times, and that the highlighting outclasses the stability adjustment for many tasks except the most complex ones
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration
No full textWhile the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running on the documents then results in documents in the svg format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete
1-Bend Upward Planar Drawings of SP-Digraphs
No full textIt is proved that every series-parallel digraph whose maximum vertex-degree is ΔΔ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of Δ distinct slopes. This is shown to be worst-case optimal in terms of the number of slopes. Furthermore, our construction gives rise to drawings with optimal angular resolution π/Δ . A variant of the proof technique is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) one-bend planar drawing with ⌈Δ/2⌉ distinct slopes if biconnected, and with ⌈Δ/2⌉+1 distinct slopes if connected
Compact Layered Drawings of General Directed Graphs
No full textWe consider the problem of layering general directed graphs under height and possibly also width constraints. Given a directed graph G=(V,A) and a maximal height, we propose a layering approach that minimizes a weighted sum of the number of reversed arcs, the arc lengths, and the width of the drawing. We call this the Compact Generalized Layering Problem (CGLP). Here, the width of a drawing is defined as the maximum sum of the number of vertices placed on a layer and the number of dummy vertices caused by arcs traversing the layer. The CGLP is NPNP -hard. We present two MIP models for this problem. The first one (EXT) is our extension of a natural formulation for directed acyclic graphs as suggested by Healy and Nikolov. The second one (CGL) is a new formulation based on partial orderings. Our computational experiments on two benchmark sets show that the CGL formulation can be solved much faster than EXT using standard commercial MIP solvers. Moreover, we suggest a variant of CGL, called MML, that can be seen as a heuristic approach. In our experiments, MML clearly improves on CGL in terms of running time while it does not considerably increase the average arc lengths and widths of the layouts although it solves a slightly different problem where the dummy vertices are not taken into account
Visibility Representations of Boxes in 2.5 Dimensions
No full textWe initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane z=0 and edges are unobstructed lines of sight parallel to the x- or y-axis. We prove that: (i) Every complete bipartite graph admits a 2.5D-BR; (ii) The complete graph Kn admits a 2.5D-BR if and only if n⩽19; (iii) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBR) which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n-vertex graph that admits a 2.5D-GBR has at most 4n−6√n edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete. The footprint of a 2.5D-BR Γ is the set of bottom faces of the boxes in Γ
Approximating the Rectilinear Crossing Number
No full textA straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G,cr(G), is the minimum number of pairs of crossing edges in any straight-line drawing of G. Determining or estimating cr¯(G) appears to be a difficult problem, and deciding if cr¯(G)≤k is known to be NP-hard. In fact, the asymptotic behavior of cr¯(Kn) is still unknown.
In this paper, we present a deterministic n2+o(1)-time algorithm that finds a straight-line drawing of any n-vertex graph G with cr¯(G)+o(n^4) pairs of crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense n-vertex graph G, one can efficiently find a straight-line drawing of G with (1+o(1))cr¯(G) pairs of crossing edges
Drawing Graphs on Few Lines and Few Planes
No full textWe investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.
- We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.
- We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).
- We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane
A Generalization of the Directed Graph Layering Problem
No full textThe Directed Layering Problem (DLP) solves a step of the widely used layer-based approach to automatically draw directed acyclic graphs. To cater for cyclic graphs, usually a preprocessing step is used that solves the Feedback Arc Set Problem (FASP) to make the graph acyclic before a layering is determined.
Here we present the Generalized Layering Problem (GLP), which solves the combination of DLP and FASP simultaneously, allowing general graphs as input. We present an integer programming model and a heuristic to solve the NP-complete GLP and perform thorough evaluations on different sets of graphs and with different implementations for the steps of the layer-based approach.
We observe that GLP reduces the number of dummy nodes significantly, can produce more compact drawings, and improves on graphs where DLP yields poor aspect ratios
