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
Upward Partitioned Book Embeddings
No full textWe analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding). Given a directed acyclic graph and a partition of its edges into k pages, can we linearly order the vertices such that the drawing is upward (a topological sort) and each page avoids crossings? We prove that the problem is NP-complete for k≥3, and for k≥4 even in the special case when each page is a matching. By contrast, the problem can be solved in linear time for k=2 pages when pages are restricted to matchings. The problem comes from Jack Edmonds (1997), motivated as a generalization of the map folding problem from computational origami
Drawing Big Graphs Using Spectral Sparsification
No full textSpectral sparsification is a general technique developed by Spielman et al. to reduce the number of edges in a graph while retaining its structural properties. We investigate the use of spectral sparsification to produce good visual representations of big graphs. We evaluate spectral sparsification approaches on real-world and synthetic graphs. We show that spectral sparsifiers are more effective than random edge sampling. Our results lead to guidelines for using spectral sparsification in big graph visualization
Optimal Compaction of Orthogonal Grid Drawings for Graphs
No full textOrthogonal graphs are used in a multitude of applications
to visualize information. Examples include database design, software engineering, VLSI layout and UML diagrams. The TSM approach is an effective methodology for creating orthogonal grid drawings of graphs. Its name is an acronym of its three stages: topology, in which a planar representation is defined; shape, when an orthogonal representation is obtained; and metrics, in which the graph’s elements are positioned on the grid in accordance to the orthogonal representation, while optimizing some characteristic of the drawing
Aligned Drawings of Planar Graphs
No full textLet G be a graph embedded in the plane and let A be an arrangement of pseudolines intersecting the drawing of G. An aligned drawing of G and A is a planar polyline drawing Γ of G with an arrangement A of lines so that Γ and A are homeomorphic to G and A. We show that if A is stretchable and every edge e either entirely lies on a pseudoline or intersects at most one pseudoline, then G and A have a straight-line aligned drawing. In order to prove these results, we strengthen the result of Da Lozzo et al. [5], and prove that a planar graph G and a single pseudoline L have an aligned drawing with a prescribed convex drawing of the outer face. We also study the more general version of the problem where only a set of vertices is given and we need to determine whether they can be collinear. We show that the problem is NP-hard but fixed-parameter tractable
Mixed Linear Layouts of Planar Graphs
No full textA k-stack (respectively, k-queue) layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout in which every edge is assigned to a stack or to a queue that use a common vertex ordering.
We disprove this conjecture by providing a planar graph that does not have such a mixed layout. In addition, we study mixed layouts of graph subdivisions, and show that every planar graph has a mixed subdivision with one division vertex per edge
Planar Drawings of Fixed-Mobile Bigraphs
No full textA fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other part, together with the edges, must be added to the drawing. We assume that G is planar and study the problem of finding, for a given k≥0, a planar poly-line drawing of G with at most k bends per edge. In the most general case, we show NP-hardness. For k=0
and under additional constraints on the positions of the fixed or mobile vertices, we either prove that the problem is polynomial-time solvable or prove that it belongs to NP. Finally, we present a polynomial-time testing algorithm for a certain type of “layered” 1-bend drawings.
Research in this work started at the Bertinoro Workshop on Graph Drawing 2016. We thank all the participants and in particular S.-H. Hong for useful discussions. We also thank an anonymous reviewer of this research for some valuable comments, and especially for suggesting the idea behind the proof of Theorem 6
BCSA: BC Tree-Based Sampling and Visualization of Big Graphs
No full textGraph sampling techniques have been popular for the analysis
and visualization of big complex networks. However, existing sampling methods often fail to preserve connectivity and important global skeletal structure in the original graph. This poster introduces two new families of sampling methods BCSA-W and BCSA-E for big complex graphs, based on the decomposition of a graph into biconnected components, known
as the BC (Block Cut-vertex) tree. Experimental results using graph sampling quality metrics show that our new sampling methods produce better results than existing methods: 25% improvement by BCSA-W and 15% by BCSA-E over existing methods on average.
We then present DBCSA, BC tree based graph sampling algorithm in distributed environment. Experiments on the Amazon Cloud EC2 demonstrate that DBCSA is scalable for big graph data sets; running time speed up of 77% for distributed 5-server sampling over sequential sampling
on average.We also present a new layout method called BCTV, which clearly shows the BC tree decomposition of a graph. Visual comparison using the BCTV layout shows that our new sampling methods can better maintain the global structure of the original graph
Arrangements of Pseudocircles: Triangles and Drawings
No full textA pseudocircle is a simple closed curve on the sphere or in the plane. The study of arrangements of pseudocircles was initiated by Grünbaum, who defined them as collections of simple closed curves that pairwise intersect in exactly two crossings. Grünbaum conjectured that the number of triangular cells p3 in digon-free arrangements of n pairwise intersecting pseudocircles is at least 2n−4. We present examples to disprove this conjecture. With a recursive construction based on an example with 12 pseudocircles and 16 triangles we obtain a family with p3(A)/n→16/11=1.45¯¯¯¯¯. We expect that the lower bound p3(A)≥4n/3 is tight for infinitely many simple arrangements. It may however be that digon-free arrangements of n pairwise intersecting circles indeed have at least 2n−4 triangles.
For pairwise intersecting arrangements with digons we have a lower bound of p3≥2n/3, and conjecture that p3≥n−1.
Concerning the maximum number of triangles in pairwise intersecting arrangements of pseudocircles, we show that p3≤2n2/3+O(n). This is essentially best possible because families of pairwise intersecting arrangements of n pseudocircles with p3/n2→2/3 as n→∞ are known.
The paper contains many drawings of arrangements of pseudocircles and a good fraction of these drawings was produced automatically from the combinatorial data produced by the generation algorithm. In the final section we describe some aspects of the drawing algorithm
3D Visibility Representations of 1-planar Graphs
No full textWe prove that every 1-planar graph G has a z-parallel visibility representation, i.e., a 3D visibility representation in which the vertices are isothetic disjoint rectangles parallel to the xy-plane, and the edges are unobstructed z-parallel visibilities between pairs of rectangles. In addition, the constructed representation is such that there is a plane that intersects all the rectangles, and this intersection defines a bar 1-visibility representation of G