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
On Degree Properties of Crossing-Critical Families of Graphs
No full textAnswering an open question from 2007, we construct infinite k-crossing-critical families of graphs which contain vertices of any prescribed odd degree, for sufficiently large k. From this we derive that, for any set of integers D such that min(D)≥3 and 3,4∈D, and for all sufficiently large k there exists a k-crossing-critical family such that the numbers in D are precisely the vertex degrees which occur arbitrarily often in any large enough graph in this family. We also investigate what are the possible average degrees of such crossing-critical families
On Minimizing Crossings in Storyline Visualizations
No full textIn a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by x-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with n characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with O(nlogn) crossings. Furthermore, we show that there exist storylines in this restricted case that require Ω(nlogn) crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixed-parameter tractable, when parameterized on the number of characters k. Our algorithm runs in time O(k!^2*klogk+k!^2*m), where m is the number of meetings
Recognizing Weighted Disk Contact Graphs
No full textDisk contact representations realize graphs by mapping vertices bijectively to interior-disjoint disks in the plane such that two disks touch each other if and only if the corresponding vertices are adjacent in the graph. Deciding whether a vertex-weighted planar graph can be realized such that the disks’ radii coincide with the vertex weights is known to be NP-hard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains NP-hard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive linear-time recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights
A Coloring Algorithm for Disambiguating Graph and Map Drawings
No full textDrawings of non-planar graphs always result in edge crossings.When there are many edges crossing at small angles, it is often difficult to follow these edges, because of the multiple visual paths resulted from the crossings that slow down eye movements. In this paper we propose an algorithm that disambiguates the edges with automatic selection of distinctive colors. Our proposed algorithm computes a near optimal color assignment of a dual collision graph, using a novel branch-and-bound procedure applied to a space decomposition of the color gamut. We conduct a user study to establish the effectiveness and limitations of this approach in clarifying drawings of real world graphs and map
Drawing Outer 1-planar Graphs with Few Slopes
No full textA graph is outer 1-planar if it admits a drawing where each vertex is on the outer face and each edge is crossed by at most another edge. Outer 1-planar graphs are a superclass of the outerplanar graphs and a subclass of the partial 3-trees. We show that an outer 1-planar graph G of bounded degree Δ admits an outer 1-planar straight-line drawing that uses O(Δ) different slopes, which extends a previous result by Knauer et al. about the planar slope number of outerplanar graphs (CGTA, 2014). We also show that O(Δ2) slopes suffice to construct a crossing-free straight-line drawing of G; the best known upper bound on the planar slope number of planar partial 3-trees of bounded degree Δ is O(Δ5) and is proved by Jelínek et al. (Graphs and Combinatorics, 2013)
The Importance of Being Proper
No full textIn this paper we study two problems related to the drawing of level graphs, that is, T -Level Planarity and Clustered-Level Planarity. We show that both problems are NP -complete in the general case and that they become polynomial-time solvable when restricted to proper instances
Trade-Offs in Planar Polyline Drawings
No full textAngular resolution, area and the number of bends are some important aesthetic criteria of a polyline drawing. Although trade-offs among these criteria have been examined over the past decades, many of these trade-offs are still not known to be optimal. In this paper we give a new technique to compute polyline drawings for planar triangulations. Our algorithm is simple and intuitive, yet implies significant improvement over the known results. We present the first smooth trade-off between the area and angular resolution for 2-bend polyline drawings of any given planar graph. Specifically, for any given n-vertex triangulation, our algorithm computes a drawing with angular resolution r/d(v) at each vertex v, and area f(n,r), for any r ∈ (0,1], where d(v) denotes the degree at v. For r 0.5, f(n,r) is less than the drawing area required by previous algorithms; f(n,r) ranges from 7.12n 2 when r ≤ 0.3 to 32.12n 2 when r = 1