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
Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
No full textWe study the classic graph drawing problem of drawing a planar graph using straight-line edges with a prescribed convex polygon as the outer face. Unlike previous algorithms for this problem, which may produce drawings with exponential area, our method produces drawings with polynomial area. In addition, we allow for collinear points on the boundary, provided such vertices do not create overlapping edges. Thus, we solve an open problem of Duncan et al., which, when combined with their work, implies that we can produce a planar straight-line drawing of a combinatorially-embedded genus-g graph with the graph's canonical polygonal schema drawn as a convex polygonal external face
On Maximum Differential Graph Coloring
No full textWe study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs
GraphML-Based Exploration and Evaluation of Efficient Parallelization Alternatives for Automation Firmware
No full textGraphs are an accepted and popular way of representing and solving problems of various kinds. Thus, applications of graphs as well as related topics such as graph visualization and graph representation are numerous. Our application is located in the domain of industrial automation and driven by the need of parallelizing our controller's firmware for the upcoming multi-core CPUs. As efficiency matters, we thereby aim at gaining maximum performance increases by spending no more implementation effort than necessary. In order to achieve that objective, we at first want to explore, evaluate and visualize those efficient parallelization alternatives by means of a graph-based model of our firmware. Thus, we are currently developing the EEEPA ( Exploration and E valuation of Efficient Parallelization Alternatives) tool for this purpose. Thereby, we have chosen and extended GraphML 1, a widespread format for graph representation
Graph Drawing Contest Report
No full textThis report describes the Annual Graph Drawing Contest, held in conjunction with the 2010 Graph Drawing Symposium in Konstanz, Germany. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology
Topology-Driven Force-Directed Algorithms
No full textThis paper studies the problem of designing graph drawing algorithms that guarantee good trade-offs in terms of number of edge crossings, crossing angle resolution, and geodesic edge tendency. It describes two heuristics designed within the topology-driven force-directed framework that combines two classical graph drawing approaches: the force-directed approach and a planarization-based approach (e.g., the topology-shape-metrics approach). An extensive experimental analysis on two different test suites of graphs shows the effectiveness of the proposed solutions for the optimization of some readability metrics
On Graphs Supported by Line Sets
No full textFor a set S of n lines labeled from 1 to n, we say that S supports an n-vertex planar graph G if for every labeling from 1 to n of its vertices, G has a straight-line crossing-free drawing with each vertex drawn as a point on its associated line. It is known from previous work [4] that no set of n parallel lines supports all n-vertex planar graphs. We show that intersecting lines, even if they intersect at a common point, are more powerful than a set of parallel lines. In particular, we prove that every such set of lines supports outerpaths, lobsters, and squids, none of which are supported by any set of parallel lines. On the negative side, we prove that no set of n lines that intersect in a common point supports all n-vertex planar graphs. Finally, we show that there exists a set of n lines in general position that does not support all n-vertex planar graphs
The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs
No full textWe study how much better a right-angled crossing (RAC) drawing of a planar graph can be than any planar drawing of the same planar graph. We analyze the area requirement, the edge-length ratio, and the angular resolution. For the first two measures, a RAC drawing can be arbitrarily much better, whereas for the third measure a RAC drawing can be 2.75 times as good
Visualizing Differences between Two Large Graphs
No full textWhen working with graphs one often faces the problem of comparing two or more graphs. For example in biology, when two protein-protein interaction networks from closely related species have to be compared, the graphs can easily contain several hundred nodes and thousands of edges but very few differences. Our goal was to develop a software-tool that creates an overview of large graphs and maintains the structure but reduces the number of nodes and edges and enables the user to easily find and investigate the areas of interest. This problem has been considered in the past by various groups ([1], [2]) and different heuristics have been proposed. Here, we follow the concept proposed in [3]. For this work, we assume that the input-graphs are relatively large with small local differences and node correspondences are known
Drawing Ordered (k - 1)-Ary Trees on k-Grids
No full textWe explore the complexity of drawing ordered (k - 1)-ary trees on grids with k directions for k E and within a given area. This includes, e.g., ternary trees drawn on the orthogonal grid. For aesthetically pleasing tree drawings on these grids, we additionally present various restrictions similar to the common hierarchical case. First, we generalize the NP-hardness of minimal width in hierarchical drawings of ordered trees to (k - 1)-ary trees on k-grids and then we generalize the Reingold and Tilford algorithm to k-grids
Lombardi Drawings of Graphs
No full textWe introduce the notion of Lombardi graph drawings, named after the American abstract artist Mark Lombardi. In these drawings, edges are represented as circular arcs rather than as line segments or polylines, and the vertices have perfect angular resolution: the edges are equally spaced around each vertex. We describe algorithms for finding Lombardi drawings of regular graphs, graphs of bounded degeneracy, and certain families of planar graphs