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
Touching Triangle Representations for 3-Connected Planar Graphs
No full textA touching triangle graph (TTG) representation of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the end vertices of e. We call Γ a proper TTG representation if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG representation. We also construct proper TTG representations for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG representation
Proportional Contact Representations of 4-Connected Planar Graphs
No full textIn a contact representation of a planar graph, vertices are represented by interior-disjoint polygons and two polygons share a non-empty common boundary when the corresponding vertices are adjacent. In the weighted version, a weight is assigned to each vertex and a contact representation is called proportional if each polygon realizes an area proportional to the vertex weight. In this paper we study proportional contact representations of 4-connected internally triangulated planar graphs. The best known lower and upper bounds on the polygonal complexity for such graphs are 4 and 8, respectively. We narrow the gap between them by proving the existence of a representation with complexity 6. We then disprove a 10-year old conjecture on the existence of a Hamiltonian canonical cycle in a 4-connected maximal planar graph, which also implies that a previously suggested method for constructing proportional contact representations of complexity 6 for these graphs will not work. Finally we prove that it is NP-hard to decide whether a 4-connected planar graph admits a proportional contact representation using only rectangles
Homotopic -Oriented Routing
No full textWe study the problem of finding non-crossing minimum-link C -oriented paths that are homotopic to a set of input paths in an environment with C -oriented obstacles. We introduce a special type of C -oriented paths—smooth paths—and present a 2-approximation algorithm that runs in O(n^2 (n + log_κ) + k in logn) time, where n is the total number of paths and obstacle vertices, k in is the total number of links in the input, and κ=|C| . The algorithm also computes an O(κ)-approximation for general C -oriented paths. As a related result we show that, given a set of C -oriented paths with L links in total, non-crossing C -oriented paths homotopic to the input paths can require a total of Ω(L logκ) links
Planar Preprocessing for Spring Embedders
No full textSpring embedders are conceptually simple and produce straight-line drawings with an undeniable aesthetic appeal, which explains their prevalence when it comes to automated graph drawing. However, when drawing planar graphs, spring embedders often produce non-plane drawings, as edge crossings do not factor into the objective function being minimized. On the other hand, there are fairly straight-forward algorithms for creating plane straight-line drawings for planar graphs, but the resulting layouts generally are not aesthetically pleasing, as vertices are often grouped in small regions and edges lengths can vary dramatically. It is known that the initial layout influences the output of a spring embedder, and yet a random layout is nearly always the default. We study the effect of using various plane initial drawings as an inputs to a spring embedder, measuring the percent improvement in reducing crossings and in increasing node separation, edge length uniformity, and angular resolution
Drawing Clustered Graphs as Topographic Maps
No full textThe 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
Many-to-One Boundary Labeling with Backbones
No full textIn this paper we study many-to-one boundary labeling with backbone leaders. In this model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points associated with this label are linked via vertical line segments to the backbone. We present algorithms for label number and leader-length minimization. If crossings are allowed, we aim to minimize their number. This can be achieved efficiently in the case of fixed label order. We show that the corresponding problem in the case of flexible label order is NP-hard
Dynamic Traceroute Visualization at Multiple Abstraction Levels
No full textWe present a system, called TPlay, for the visualization of the traceroutes performed by the Internet probes deployed by active measurement projects. These traceroutes are continuously executed towards selected Internet targets. TPlay allows to look at traceroutes at different abstraction levels and to animate the evolution of traceroutes during a selected time interval. The system has been extensively tested on traceroutes performed by RIPE Atlas [22] Internet probes
New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs
No full textA topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-planar graph with n vertices and no pair of edges intersecting in more than O(1) points has at most n(logn) O(logk) edges. We improve this upper bound to 2α(n)cnlogn , where α(n) denotes the inverse Ackermann function, and c depends only on k. We also show that every k-quasi-planar graph with n vertices and every two edges have at most one point in common has at most O(nlogn) edges. This improves the previously known upper bound of 2α(n)cnlogn obtained by Fox, Pach, and Suk
Graph Drawing Contest Report
No full textThis report describes the 19th Annual Graph Drawing Contest, held in conjunction with the 2012 Graph Drawing Symposium in Redmond, USA. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology. For the first time, we introduced a graph drawing game contest and asked conference attendees to judge the games
Counting Plane Graphs: Cross-Graph Charging Schemes
No full textWe study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have been recently applied to obtain various properties of triangulations that are embedded over a fixed set of points in the plane. We show how this method can be generalized to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of for the maximum number of crossing-free straight-edge graphs that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound 207.85^N in Hoffmann et al.[14]). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded over a specific point set.
We then show how to apply the cross-graph charging-scheme method for graphs that allow certain types of crossings. Specifically, we consider graphs with no set of k pairwise-crossing edges (more commonly known as k-quasi-planar graphs). For k=3 and k=4, we prove that, for any set S of N points in the plane, the number of graphs that have a straight-edge k-quasi-planar embedding over S is only exponential in N