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
Superpatterns and Universal Point Sets
No full textAn old open problem in graph drawing asks for the size of a universal point set, a set of points that can be used as vertices for straight-line drawings of all n-vertex planar graphs. We connect this problem to the theory of permutation patterns, where another open problem concerns the size of superpatterns, permutations that contain all patterns of a given size. We generalize superpatterns to classes of permutations determined by forbidden patterns, and we construct superpatterns of size n 2/4 + Θ(n) for the 213-avoiding permutations, half the size of known superpatterns for unconstrained permutations. We use our superpatterns to construct universal point sets of size n 2/4 − Θ(n), smaller than the previous bound by a 9/16 factor. We prove that every proper subclass of the 213-avoiding permutations has superpatterns of size O(nlog O(1) n), which we use to prove that the planar graphs of bounded pathwidth have near-linear universal point sets
Drawing Non-Planar Graphs with Crossing-Free Subgraphs
No full textWe initiate the study of the following problem: Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing Γ of G in the plane such that the edges of S are not crossed in Γ? We give positive and negative results for different kinds of spanning subgraphs S of G. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of G ∖ S; in this setting different trade-offs between number of bends and drawing area are given
Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases
No full textCrossing minimization is one of the central problems in graph drawing. Recently, there has been an increased interest in the problem of minimizing crossings between paths in drawings of graphs. This is the metro-line crossing minimization problem (MLCM): Given an embedded graph and a set L of simple paths, called lines, order the lines on each edge so that the total number of crossings is minimized. So far, the complexity of MLCM has been an open problem. In contrast, the problem variant in which line ends must be placed in outermost position on their edges (MLCM-P) is known to be NP-hard.
Our main results answer two open questions: (i) We show that MLCM is NP-hard. (ii) We give an O(log|L|−−−−−−√) -approximation algorithm for MLCM-P
On Orthogonally Convex Drawings of Plane Graphs (Extended Abstract)
No full textWe investigate the bend minimization problem with respect to a new drawing style called orthogonally convex drawing, which is orthogonal drawing with an additional requirement that each inner face is drawn as an orthogonally convex polygon. For the class of bi-connected plane graphs of maximum degree 3, we give a necessary and sufficient condition for the existence of a no-bend orthogonally convex drawing, which in turn, enables a linear time algorithm to check and construct such a drawing if one exists. We also develop a flow network formulation for bend-minimization in orthogonally convex drawings, yielding a polynomial time solution for the problem. An interesting application of our orthogonally convex drawing is to characterize internally triangulated plane graphs that admit floorplans using only orthogonally convex modules subject to certain boundary constraints
Graph Drawing Contest Report
No full textThis report describes the 20th Annual Graph Drawing Contest, held in conjunction with the 2013 Graph Drawing Symposium in Bordeaux (Talence), France. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology
On Representing Graphs by Touching Cuboids
No full textWe consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids
Covering Paths for Planar Point Sets
No full textGiven a set of points, a covering path is a directed polygonal path that visits all the points. We show that for any n points in the plane, there exists a (possibly self-crossing) covering path consisting of straight line segments. If no three points are collinear, any covering path (self-crossing or non-crossing) needs at least segments. If the path is required to be non-crossing, straight line segments obviously suffice and we exhibit n-element point sets which require at least segments in any such path. Further, we show that computing a non-crossing covering path for n points in the plane requires Ω(n logn) time in the worst case
Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings
No full textWe extend the notion of canonical orderings to cylindric triangulations. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix, Pach and Pollack to this setting. Our algorithm yields in linear time a crossing-free straight-line drawing of a cylindric triangulation G with n vertices on a regular grid , with and , where d is the (graph-) distance between the two boundaries. As a by-product, we can also obtain in linear time a crossing-free straight-line drawing of a toroidal triangulation with n vertices on a periodic regular grid, with and , where c is the length of a shortest non-contractible cycle. Since , the grid area is . Our algorithms apply to any triangulation (whether on the cylinder or on the torus) that have no loops nor multiple edges in the periodic representation
Clustering, Visualizing, and Navigating for Large Dynamic Graphs
No full textIn this paper, we present a new approach to exploring dynamic graphs. We have developed a new clustering algorithm for dynamic graphs which finds an ideal clustering for each time-step and links the clusters together. The resulting time-varying clusters are then used to define two visual representations. The first view is an overview that shows how clusters evolve over time and provides an interface to find and select interesting time-steps. The second view consists of a node link diagram of a selected time-step which uses the clustering to efficiently define the layout. By using the time-dependant clustering, we ensure the stability of our visualization and preserve user mental map by minimizing node motion, while simultaneously producing an ideal layout for each time step. Also, as the clustering is computed ahead of time, the second view updates in linear time which allows for interactivity even for graphs with upwards of tens of thousands of nodes
Optical Graph Recognition
No full textOptical graph recognition (OGR) reverses graph drawing. A drawing transforms the topological structure of a graph into a graphical representation. Primarily, it maps vertices to points and displays them by icons and it maps edges to Jordan curves connecting the endpoints. OGR transforms the digital image of a drawn graph into its topological structure. It consists of four phases, preprocessing, segmentation, topology recognition, and postprocessing. OGR is based on established digital image processing techniques. Its novelty is the topology recognition where the edges are recognized with emphasis on the attachment to their vertices and on edge crossings.
Our prototypical implementation shows the effectiveness of the approach and produces a GraphML file which can be used for further algorithmic studies and graph drawing tools