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
Characterization of Unlabeled Radial Level Planar Graphs
No full textSuppose that an n-vertex graph has a distinct labeling with the integers {1, . . . , n}. Such a graph is radial level planar if it admits a crossings-free drawing under two constraints. First, each vertex lies on a concentric circle such that the radius of the circle equals the label of the vertex. Second, each edge is drawn with a radially monotone curve. We characterize the set of unlabeled radial level planar (URLP) graphs that are radial level planar in terms of 7 and 15 forbidden subdivisions depending on whether the graph is disconnected or connected, respectively. We also provide linear-time drawing algorithms for any URLP graph
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
No full textIt is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree Δ. We show that the planar slope number of every series-parallel graph of maximum degree three is three. We also show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is c at most 2O(Δ) . In particular, we answer the question of Dujmovi´ et al. [Computational Geometry 38 (3), pp. 194–212 (2007)] whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f (Δ) slopes. Keywords: graph drawing; planar graphs; slopes; planar slope number
Why Are String Graphs So Beautiful? (Extended Abstract)
No full textString graphs are intersection graphs of continuous simple arcs (”strings”) in the plane. They may have a complicated structure,they have no good characterization, the recognition of string graphs is an NP-complete problem. Yet these graphs show remarkably beautiful
properties from the point of view of extremal graph theory. What is the explanation for this phenomenon? We do not really know, so we offer three answers. (1) Being a string graph is a hereditary property. (2) String graphs are nicely separable into smaller pieces. (3) As in any geometric picture, one can discover several natural partial orders on a collection of strings
Placing Text Boxes on Graphs: A Fast Approximation Algorithm for Maximizing Overlap of a Square and a Simple Polygon
No full textIn this paper we consider the problem of placing a unit square on a face of a drawn graph bounded by n vertices such that the area of overlap is maximized. Exact algorithms are known that solve this problem in O(n2 ) time. We present an approximation algorithm that— for any given ǫ > 0—places a (1 + ǫ)-square on the face such that the area of overlap is at least the area of overlap of a unit square in an optimal placement. The algorithm runs in O( 1 n log2 n) time. Extensions of the ǫ / √ algorithm solve the problem for unit discs, using O( log(1ǫ ǫ) n log2 n) time, ǫ and for bounded aspect ratio rectangles of
unit area, using O( ǫ1 n log2 n) 2 time
Networks in Biology – from Identification, Analysis to Interpretation
No full textOver the last decade networks has become a unifying language in biology. Yet we are only in the beginning of understanding their significance for biology and their medical applications. I will talk about the diversity of biological networks composed either of genes, proteins, metabolites, or cells and the associated methods for finding these graphs in the data. Next I will provide an overview of different methods of analysis and what kind of insights that have been obtained. During the talk I will highlight current challenging problems requiring computational skills with respect to identification, analysis, algorithms, visualization and software
Succinct Greedy Graph Drawing in the Hyperbolic Plane
No full textWe describe a method for producing a greedy embedding of any n- vertex simple graph G in the hyperbolic plane, so that a message M between any pair of vertices may be routed by having each vertex that receives M pass it to a neighbor that is closer to M ’s destination. Our algorithm produces succinct drawings, where vertex positions are represented using O(log n) bits and distance comparisons may be performed efficiently using these representations
Removing Node Overlaps Using Multi-Sphere Scheme
No full textIn this paper, we consider the problem of removing overlaps of labels in a given layout by changing locations of some of the overlapping labels, and present a new method for the problem based on a packing approach, called multi-sphere scheme. More specifically, we study two new variations of the label overlap problem, inspired by real world applications, and provide a solution to each problem. Our new approach is very flexible to support various operations such as translation, translation with direction constraints, and rotation. Further, our method can support labels with arbitrary shapes in both 2D and 3D layout settings. Our extensive experimental results show that our new approach is very effective for removing label overlaps
DAGmap View
No full textDAGmap view is a program written in Java that draws directed acyclic graphs using space filling techniques. In DAGmap view the layout function and the hierarchy presentation function have been decomposed to improve the stability of the layout during navigation and zooming
Connected Rectilinear Graphs on Point Sets
No full textGiven n points in d-dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d = 2 we present an algorithm for computing these directions (if they exist) in O(n2 ) tim