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
C-Planarity of Extrovert Clustered Graphs
No full textA clustered graph has its vertices grouped into clusters in a hierarchical way via subset inclusion, thereby imposing a tree structure on the clustering relationship. The c-planarity problem is to determine if such a graph can be drawn in a planar way, with clusters drawn as nested regions and with each edge (drawn as a curve between vertex points) crossing the boundary of each region at most once. Unfortunately, as with the graph isomorphism problem, it is open as to whether the c-planarity problem is NP-complete or in P. In this paper, we show how to solve the c-planarity problem in polynomial time for a new class of clustered graphs, which we call emph{extrovert} clustered graphs. This class is quite natural (we argue that it captures many clustering relationships that are likely to arise in practice) and includes the clustered graphs tested in previous work by Dahlhaus as well as Feng, Eades, and Cohen. Interestingly, this class of graphs does not include, nor is it included by, a class studied recently by Gutwenger extit{et al.}, therefore, this paper offers a alternative advancement in our understanding of the efficient drawability of clustered graphs in a planar way. Our testing algorithm runs in O(n^3) time, implies an embedding algorithm with the same time complexity, and can be easily implemented
A New Method for Efficiently Generating Planar Graph Visibility Representations
No full textA planar graph visibility representation maps each vertex to a horizontal segment at a vertical position and each edge to a vertical segment at a horizontal position such that each edge segment terminates at the vertical positions of its endpoint vertices and intersects no other horizontal vertex segments. [part of Introduction
Non-Planar Core Reduction of Graphs
No full textWe present a reduction method that reduces a graph to a smaller core graph which behaves invariant with respect to planarity measures like crossing number, skewness, and thickness. The core reduction is based on the decomposition of a graph into its triconnected components and can be computed in linear time. It has applications in heuristic and exact optimization algorithms for the planarity measures mentioned above. Experimental results show that this strategy yields a reduction to 2/3 in average for a widely used benchmark set of graphs
Applications of Parameterized st-Orientations in Graph Drawing Algorithms
No full textMany graph drawing algorithms use st-numberings (st-orientations or bipolar orientations) as a first step. An st-numbering of a biconnected undirected graph defines a directed graph with no cycles, one single source s and one single sink t. As there exist exponentially many st-numberings that correspond to a certain undirected graph G, using different st-numberings in various graph drawing algorithms can result in aesthetically different drawings with different area bounds. In this paper, we present results concerning new algorithms for parameterized st-orientations, their impact on graph drawing algorithms and especially in visibility representations
Odd Crossing Number Is Not Crossing Number
No full textThe crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the {em odd crossing number}. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems)
BLer: A Boundary Labeller for Technical Drawings
No full textBLer is a prototype tool aiming to automate the boundary labelling process[1]. It targets the area of technical and medical drawings, where it is often common to explain certain features of the drawing by blocks of text that are arranged on its boundary
Visualizing Graphs as Trees: Plant a Seed and Watch It Grow
No full textTreePlus is a graph browsing technique based on a tree-style layout. It shows the missing graph structure using interaction techniques and enables users to start with a specific node and incrementally explore the local structure of graphs. We believe that it supports particularly well tasks that require rapid reading of labels
A Multi-Graph Approach to Complexity Management in Interactive Graph Visualization
No full textIn this paper we describe a new, multi-graph approach for development of a comprehensive set of complexity management techniques for interactive graph visualization tools. This framework facilitates efficient implementation of management of multiple associated graphs with navigation links and nesting of graphs as well as ghosting, folding and hiding of unwanted graph elements. The theoretical analyses show that the involved data structures and operations on them are quite efficient, and an implementation in a graph drawing tool has proven to be successful
Layout effects on sociogram perception
No full textThis paper describes a within-subjects experiment in which we compare the relative effectiveness of five sociogram drawing conventions in communicating underlying network substance, based on user task performance and usability preference, in order to examine effects of different spatial layout formats on human sociogram perception. We also explore the impact of edge crossings, a widely accepted readability aesthetic. Subjective data were gathered based on the methodology of Purchase [2002]. Objective data were collected through an online system. We found that both edge crossings and conventions pose significant affects on user preference and task performance of finding groups, but either has little impact on the perception of actor status. On the other hand, the node positioning and angular solution might be more important in perceiving actor status. In visualising social networks, it is important to note that the techniques that are highly preferred by users do not necessarily always produce best task performance
No-Bend Orthogonal Drawings of Series-Parallel Graphs
No full textIn a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. Every series-parallel graph is planar. In this paper we give a linear-time algorithm to examine whether a series-parallel graph G of the maximum degree three has a no-bend orthogonal drawing and to find one if G has