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
The Partial Visibility Representation Extension Problem
No full textFor a graph G, a function ψ is called a bar visibility representation of G when for each vertex v∈V(G), ψ(v) is a horizontal line segment (bar) and uv∈E(G) iff there is an unobstructed, vertical, ε-wide line of sight between ψ(u) and ψ(v). Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation ψ of G, additionally, for each directed edge (u, v) of G, puts the bar ψ(u) strictly below the bar ψ(v). We study a generalization of the recognition problem where a function ψ′ defined on a subset V′ of V(G) is given and the question is whether there is a bar visibility representation ψ of G with ψ|V′=ψ′. We show that for undirected graphs this problem together with closely related problems are NP
-complete, but for certain cases involving directed graphs it is solvable in polynomial time
Ortho-Polygon Visibility Representations of Embedded Graphs
No full textAn ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. Namely, we prove that if G is 1-plane (i.e., it has at most one crossing per edge) an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute in O(n) time an OPVR of G whose vertex complexity is bounded by a constant. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed. Finally, we present the results of an experimental study on the vertex complexity of OPVRs of 1-plane graphs
1-Bend RAC Drawings of 1-Planar Graphs
No full textA graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles. The relationships between 1-planar graphs and RAC drawings have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC drawable and graphs that have a straight-line RAC drawing but that are not 1-planar [22]. Also, straight-line RAC drawings always exist for IC-planar graphs [9], a subclass of 1-planar graphs. One of the main questions still open is whether every 1-planar graph has a RAC drawing with at most one bend per edge. We positively answer this question
A Note on the Practicality of Maximal Planar Subgraph Algorithms
No full textGiven a graph G, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of G with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but—to the best of our knowledge—they have never been compared competitively in practice.
We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice
The Crossing Number of the Cone of a Graph
No full textMotivated by a problem asked by Richter and by the long standing Harary-Hill conjecture, we study the relation between the crossing number of a graph G and the crossing number of its cone CG, the graph obtained from G by adding a new vertex adjacent to all the vertices in G. Simple examples show that the difference cr(CG)−cr(G) can be arbitrarily large for any fixed k=cr(G). In this work, we are interested in finding the smallest possible difference, that is, for each non-negative integer k, find the smallest f(k) for which there exists a graph with crossing number at least k and cone with crossing number f(k). For small values of k, we give exact values of f(k) when the problem is restricted to simple graphs, and show that f(k)=k+Θ(√k) when multiple edges are allowed
A Simple Quasi-planar Drawing of K10
No full textWe show that the complete graph on ten vertices K10 is a simple quasi-planar graph, which answers a question of Ackerman and Tardos [E. Ackerman and G. Tardos, On the maximum number of edges in quasi-planar graphs, J. Comb. Theory, Series A 114 (2007) 563–571]and shows that the bound 6.5n−20 on the maximum number of edges of simple quasi-planar graphs is tight for
n=10
A Distributed Multilevel Force-Directed Algorithm
No full textThe wide availability of powerful and inexpensive cloud computing services naturally motivates the study of distributed graph layout algorithms, able to scale to very large graphs. Nowadays, to process Big Data, companies are increasingly relying on PaaS infrastructures rather than buying and maintaining complex and expensive hardware. So far, only a few examples of basic force-directed algorithms that work in a distributed environment have been described. Instead, the design of a distributed multilevel force-directed algorithm is a much more challenging task, not yet addressed. We present the first multilevel force-directed algorithm based on a distributed vertex-centric paradigm, and its implementation on Giraph, a popular platform for distributed graph algorithms. Experiments show the effectiveness and the scalability of the approach. Using an inexpensive cloud computing service of Amazon, we draw graphs with ten million edges in about 60 min
Snapping Graph Drawings to the Grid Optimally
No full textIn geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This process is called snapping to the grid and has been investigated thoroughly from a computational-geometry perspective. In this paper we investigate the same problem for given drawings of planar graphs under the restriction that their combinatorial embedding must be kept and edges are drawn straight-line. We show that the problem is NP-hard for several objectives and provide an integer linear programming formulation. Given a plane graph G and a positive integer w, our ILP can also be used to draw G straight-line on a grid of width w and minimum height (if possible)
Beyond Level Planarity
No full textIn this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity, are polynomial-time solvable.
Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels