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
Placing Edge Labels by Modifying an Orthogonal Graph Drawing
No full textIn this paper we investigate how one can modify an orthogonal graph drawing to accommodate the placement of overlap-free labels with the minimum cost. We present a polynomial time algorithm that finds the minimum increase of space in one direction, needed to resolve overlaps, while preserving the orthogonal representation of the drawing
Orthogonal Graph Drawing with Flexibility Constraints
No full textIn this work we consider the following problem. Given a planar graph G with maximum degree 4 and a function flex E->N_o: that gives each edge a flexibility. Does G admit a planar embedding on the grid such that each edge e has at most flex(e) bends? Note that in our setting the combinatorial embedding of G is not fixed. We give a polynomial-time algorithm for this problem when the flexibility of each edge is positive. This includes as a special case the problem of deciding whether G admits a drawing with at most one bend per edge
Confluent Drawing Algorithms Using Rectangular Dualization
No full textThe need of effective drawings for non-planar dense graphs is motivated by the wealth of applications in which they occur, including social network analysis, security visualization and web clustering engines, just to name a few. One common issue graph drawings are affected by is the visual clutter due to the high number of (possibly intersecting) edges to display. Confluent drawings address this problem by bundling groups of edges sharing the same path, resulting in a representation with less edges and no edge intersections. In this paper we describe how to create a confluent drawing of a graph from its rectangular dual and we show two important advantages of this approach
GVSR: An On-Line Guide for Choosing a Graph Visualization Software
No full textIt is easy to find graph visualization applications for all sorts of uses. However, choosing an appropriate application may be difficult. This poster presents a website ( http://gvsr.polytech.univ-nantes.fr/ ) built to help users to choose a program adapted to their problems. So far, this site references eighty programs and aims at helping users both in their choices and in comparing the programs. The site is also designed as a tool repository helping the community to access and compare the available tools, and benchmark new techniques and algorithms
Optimal k-Level Planarization and Crossing Minimization
No full textAn important step in laying out hierarchical network diagrams is to order the nodes on each level. The usual approach is to minimize the number of edge crossings. This problem is NP-hard even for two layers when the first layer is fixed. Hence, in practice crossing minimization is performed using heuristics. Another suggested approach is to maximize the planar subgraph, i.e. find the least number of edges to delete to make the graph planar. Again this is performed using heuristics since minimal edge deletion for planarity is NP-hard. We show that using modern SAT and MIP solving approaches we can find optimal orderings for minimal crossing or minimal edge deletion for planarization on reasonably sized graphs. These exact approaches provide a benchmark for measuring quality of heuristic crossing minimization and planarization algorithms. Furthermore, we can straightforwardly extend our approach to minimize crossings followed by maximizing planar subgraph or vice versa; these hybrid approaches produce noticeably better layout then either crossing minimization or planarization alone
Complexity of Finding Non-Planar Rectilinear Drawings of Graphs
No full textWe study the complexity of the problem of finding non-planar rectilinear drawings of graphs. This problem is known to be NP-complete. We consider natural restrictions of this problem where constraints are placed on the possible orientations of edges. In particular, we show that if each edge has prescribed direction "left" , "right" , "down" or "up" , the problem of finding a rectilinear drawing is polynomial, while finding such a drawing with the minimum area is NP-complete. When assigned directions are "horizontal" or "vertical" or a cyclic order of the edges at each vertex is specified, the problem is NP-complete. We show that these two NP-complete cases are fixed parameter tractable in the number of vertices of degree 3 or 4
How to Draw a Tait-Colorable Graph
No full textPresented here are necessary and sufficient conditions for a cubic graph equipped with a Tait-coloring to have a drawing in the real projective plane where every edge is represented by a line segment, all of the lines supporting the edges sharing a common color are concurrent, and all of the supporting lines are distinct
An Experimental Evaluation of Multilevel Layout Methods
No full textApplying the multilevel paradigm to energy-based layout algorithms can improve both the quality of the resulting drawings as well as the running time of the layout computation. In order to do this, approaches for the different multilevel phases refinement, placement, layout, and optionally scaling and postprocessing need to be implemented. A number of multilevel layout algorithms have been proposed already, which differ in the way these phases are realized. We present an experimental study that investigates the influence of varying combinations with respect to running time and quality criteria
Automatic Generation of Route Sketches
No full textGenerating route sketches is a graph redrawing problem, where we are given an initial drawing of a graph G and want to find a new, schematized drawing of G that reduces the drawing complexity while preserving the structural characteristics of the input. The motivation of our work is the visualization of routes in road networks as sketches for driving directions. An important property of a route sketch is that it focuses on road changes and important landmarks rather than exact geography and distances. Typically the start and destination lie in populated areas that are locally reached via a sequence of relatively short road segments. On the other hand, the majority of the route typically consists of long highway segments with no or only few road changes. This property makes it difficult to display driving directions for the whole route in a single traditional map since some areas require much smaller scales than others. The strength of route sketches for this purpose is that they are not drawn to scale but rather use space proportionally to the route complexity
Comparative Visualization of User Flows in Voice Portals
No full textVoice portals are widely used to guide users interactively through an application. Recent portals provide a growing number of functions in one application, thus increasing their complexity. This work presents flow-map-based techniques for the comparative visualization of user flows at different time frames, in order to enable dialog designers to analyze and improve the user interaction with these systems. Natural Language Systems in Voice Portals: More sophisticated voice portals use natural language systems (NLS), giving users the option to actually talk to the system in whole sentences. The system tries to interpret these sentences and interactively asks the user for detailed information, if necessary. Portals using NLS are rather large and complex, making it difficult to analyze their performance. Especially after applying changes to a voice portal or in case of technical problems, it is important to be able to analyze the consequences on user flows in the system