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
Tree Drawings on the Hexagonal Grid
No full textWe consider straight-line drawings of trees on a hexagonal grid. The hexagonal grid is an extension of the common grid with inner nodes of degree six. We restrict the number of directions used for the edges from each node to its children from one to five, and to five patterns: straight, Y , ψ , X , and full. The ψ - drawings generalize hv - or strictly upward drawings to ternary trees. We show that complete ternary trees have a ψ-drawing on a square of size O(n1.262 ) and general ternary trees can be drawn within O(n1.631 ) area. Both bounds are optimal. Sub- quadratic bounds are also obtained for X- pattern drawings of complete tetra trees, and for full- pattern drawings of complete penta trees, which are 4- ary and 5- ary trees. These results parallel and complement the ones of Frati [8] for straight- line orthogonal drawings of ternary trees. Moreover, we provide an algorithm for compacted straight- line drawings of penta trees on the hexagonal grid, such that the direction of the edges from a node to its children is given by our patterns and these edges have the same length. However, drawing trees on a hexagonal grid within a prescribed area or with unit length edges is N P -hard
Isometric Diamond Subgraphs
No full textWe test in polynomial time whether a graph embeds in a distance-preserving way into the hexagonal tiling, the three-dimensional diamond structure, or analogous higher-dimensional structures
Dunnart: A Constrained- Based Network Diagram Authoring Tool
No full textWe present a new network diagram authoring tool, Dunnart, that provides continuous network layout. It continuously adjusts the layout in response to user interaction, while still maintaining the layout style and, where reasonable, the current layout topology. The diagram author uses placement constraints, such as alignment and distribution, to tailor the layout style and can guide the layout by repositioning diagram components or rerouting connectors. The key to the flexibility of our approach is the use of topology-preserving constrained graph layout
Crossing Number of Graphs with Rotation Systems
No full textWe show that computing the crossing number of a graph with a given rotation system is NP-complete. This result leads to a new and much simpler proof of Hlinvený's result, that computing the crossing number of a cubic graph (without rotation system) is NP-complete. We also investigate the special case of multigraphs with rotation systems on a fixed number of vertices. For k=1 and k=2 the crossing number can be computed in polynomial time and approximated to within a factor of 2 in linear time. For larger k we show how to approximate the crossing number to within a factor of k+4choose 4/5 in time O(m^k+2) on a graph with m edges
Polynomial Area Bounds for MST embeddings of trees
No full textIn their seminal paper on geometric minimum spanning trees, Monma and Suri [6] gave a method to embed any tree of maximal degree 5 as a minimum spanning tree in the Euclidean plane. They derived area bounds of O(2^k^2 times 2^k^2) for trees of height and conjectured that an improvement below is not possible for some constant . We partially disprove this conjecture by giving polynomial area bounds for arbitrary trees of maximal degree 3 and 4
Drawing Colored Graphs with Contrained Vertex Positions and Few Bends per Edge
No full textHamiltonicity, book embeddability, and point-set embeddability of planar graphs are strictly related concepts. We exploit the interplay between these notions to describe colored sets of points and to design polynomial-time algorithms to embed -colored planar graphs on these sets such that the resulting drawings have bends per edge
Treemaps for Directed Acyclic Graphs
No full textGene Ontology information related to the biological role of genes is organized in a hierarchical manner that can be represented by a directed acyclic graph (DAG). Treemaps graphically represent hierarchical information via a two-dimensional rectangular map. They
efficiently display large trees in limited screen space. Treemaps have been used to visualize the Gene Ontology by first transforming the DAG into a tree. However this transformation has several undesirable effects such as producing trees with a large number of nodes and scattering the rectangles associated with the duplicates of a node around the screen. In this paper we introduce the problem of visualizing a DAG as a treemap, we present two special cases, and we discuss complexity results
Line Crossing Minimization on Metro Maps
No full textWe consider the problem of drawing a set of simple paths along the edges of an embedded underlying graph G=(V,E), so that the total number of crossings among pairs of paths is minimized. This problem arises when drawing metro maps, where the embedding of G depicts
the structure of the underlying network, the nodes of G correspond to train stations, an edge connecting two nodes implies that there exists a railway line which connects them, whereas the paths illustrate the lines connecting terminal stations. We call this the metro-line crossing minimization problem (MLCM).
In contrast to the problem of drawing the underlying graph nicely, MLCM has received fewer attention. It was recently introduced by Benkert et. al in [4]. In this paper, as a first step towards solving MLCM in arbitrary graphs, we study path and tree networks. We examine several variations of the problem for which we develop algorithms for obtaining optimal solutions
Multi-Circular Layout of Micro/Macro Graphs
No full textWe propose a layout algorithm for micro/macro graphs, i.e. relational structures with two levels of detail. While the micro-level graph is given, the macro-level graph is induced by a given partition of the micro-level vertices. A typical example is a social network of employees organized into different departments. We do not impose restrictions on the macro-level layout other than sufficient thickness of edges and vertices, so that the micro-level graph can be placed on top of the macro-level graph. For the micro-level graph we define a combinatorial multi-circular embedding and present corresponding layout algorithms based on edge crossing reduction strategies
Simultaneous Geometric Graph Embeddings
No full textWe consider the following problem known as simultaneous geometric graph embedding (SGE). Given a set of planar graphs on a shared vertex set, decide whether the vertices can be placed in the plane in such a way that for each graph the straight-line drawing is planar. We partially settle an open problem of Erten and Kobourov [5] by showing that even for two graphs the problem is NP-hard.
We also show that the problem of computing the rectilinear crossing number of a graph can be reduced to a simultaneous geometric graph embedding problem; this implies that placing SGE in NP will be hard, since the corresponding question for rectilinear crossing number is a long-standing open problem. However, rather like rectilinear crossing number, SGE can be decided in PSPACE