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
Classification of Planar Upward Embedding
No full textWe consider planar upward drawings of directed graphs on arbitrary surfaces where the upward direction is defined by a vector field. This generalizes earlier approaches using surfaces with a fixed embedding in R3 and introduces new classes of planar upward drawable graphs, where some of them even allow cycles. Our approach leads to a classifi-
cation of planar upward embeddability. In particular, we show the coincidence of the classes of planar upward drawable graphs on the sphere and on the standing cylinder. These classes coincide with the classes of planar upward drawable graphs with a homogeneous field on a cylinder and with a radial field in the plane. A cyclic field in the plane introduces the new class RUP of upward drawable graphs, which can be embedded on a rolling cylinder. We establish strict inclusions for planar upward drawability on the plane, the sphere, the rolling cylinder, and the torus, even for acyclic graphs. Finally, upward drawability remains NP-hard for the standing cylinder and the torus; for the cylinder this was left as an open problem by Limaye et al
Combining Problems on RAC Drawings and Simultaneous Graph Drawings
No full textWe present an overview of the first combinatorial results for the so-called geometric RAC simultaneous drawing problem (or GRacSim drawing problem, for short), i.e., a combination of problems on geometric RAC drawings [3] and geometric simultaneous graph drawings [2]. According to this problem, we are given two planar graphs G 1 = (V, E 1) and G 2 = (V, E 2) that share a common vertex set but have disjoint edge sets, i.e., E 1 ⊆ V ×V , E 2 ⊆ V ×V and E 1 ∩ E 2 = ∅ The main task is to place the vertices on the plane so that, when the edges are drawn as straight-lines, (i) each graph is drawn planar, (ii) there are no edge overlaps, and, (iii) crossings between edges in E 1 and E 2 occur at right angles
Kozo Sugiyama 1945 - 2011
No full textKozo Sugiyama was born in Gifu Prefecture Japan on September 17, 1945. He received his B.S., M.S., and Dr. Sci. at Nagoya University in 1969, 1971, 1974 respectively. For 23 years from 1974 he was a researcher at Fujitsu. During this time he spent a year at the International Institute for Applied Systems Analysis in Laxenburg in Austria. In the mid 1990s he served as the Director of the Information Processing Society of Japan. In 1997 he moved from Fujitsu to the newly-created Japan Advanced Institute of Science and Technology. His first position there was Professor of the School of Knowledge Science, but he soon became Director of the Center for Knowledge Science, and then Dean of the School of Knowledge Science. His last few years at JAIST were spent as a Vice President of the University
Advances in the Planarization Method: Effective Multiple Edge Insertions
No full textThe planarization method is the strongest known method to heuristically find good solutions to the general crossing number problem in graphs: starting from a planar subgraph, one iteratively inserts edges,representing crossings via dummy nodes. In the recent years, several improvements both from the practical and the theoretical point of view have been made. We review these advances and conduct an extensive study of the algorithms’ practical implications. Thereby, we present the first implementation of an approximation algorithm for the crossing number problem of general graphs, and compare the obtained results with known exact crossing number solutions
Optimizing a Radial Layout of Bipartite Graphs for a Tool Visualizing Security Alerts
No full textEffective tools are crucial for visualizing large quantities of information. While developing these tools, numerous graph drawing problems emerge. We present solutions for reducing clutter in a radial visualization of a bipartite graph representing the alerts generated by an IDS protecting a computer network. Our solutions rely essentially on (i) unambiguous edge bundling to reduce the number of edges to display and (ii) the minimization of the total sum of the edge lengths
Upward Planarity Testing of Embedded Mixed Graphs
No full textA mixed graph has both directed and undirected edges. We study an upward planarity testing problem for embedded mixed graphs and solve it using Integer Linear Programming. Experiments show the efficiency of our technique
Graph Drawing Contest Report
No full textThis report describes the 18th Annual Graph Drawing Contest, held in conjunction with the 2011 Graph Drawing Symposium in Eindhoven, the Netherlands. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology
Drawing Clustered Graphs as Topographic Maps
Get PDFThe visualization of clustered graphs is an essential tool for the analysis of networks, in particular, social networks, in
which clustering techniques like community detection can reveal various structural properties.
In this paper, we show how clustered graphs can be drawn as topographic maps, a type of map easily understandable by users not
familiar with information visualization. Elevation levels of connected entities correspond to the nested structure of the cluster hierarchy.
We present methods for initial node placement and describe a tree mapping based algorithm that produces an area efficient layout.
Given this layout, a triangular irregular mesh is generated that is used to extract the elevation data for rendering the map. In addition,
the mesh enables the routing of edges based on the topographic features of the map.
We also discuss the pitfalls we encountered on the way from the initial idea to the current version of the experimental software that is
able to deal with large social networks. We demonstrate this with our visualizations of benchmark instances
Triangulations with Circular Arcs
No full textAn important objective in the choice of a triangulation is that the smallest angle becomes as large as possible. In the straight-line case, it is known that the Delaunay triangulation is optimal in this respect. We propose and study the concept of a circular arc triangulation— a simple and effective alternative that offers flexibility for additionally enlarging small angles—and discuss its applications in graph drawing
Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane
No full textThis paper considers the problem of embedding trees into the hyperbolic plane. We show that any tree can be realized as the Delaunay graph of its embedded vertices. Particularly, a weighted tree can be embedded such that the weight on each edge is realized as the hyperbolic distance between its embedded vertices. Thus the embedding preserves the metric information of the tree along with its topology. The distance distortion between non adjacent vertices can be made arbitrarily small – less than a (1 + ε) factor for any given ε. Existing results on low distortion of embedding discrete metrics into trees carry over to hyperbolic metric through this result. The Delaunay character implies useful properties such as guaranteed greedy routing and realization as minimum spanning trees