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 Planar Graphs with Many Collinear Vertices
No full textGiven a planar graph G, what is the maximum number of collinear vertices in a planar straight-line drawing of G? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known: Every n-vertex planar graph has a planar straight-line drawing with Ω(√n) collinear vertices; for every n, there is an n-vertex planar graph whose every planar straight-line drawinghas O(n^0.986) collinear vertices; every n-vertex planar graph of treewidth at most two has a planar straight-line drawingwith Θ(n) collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs, partially answering two problems posed by Ravsky and Verbitsky. Similar results are not possible for all bounded treewidth or bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems
Algorithms for Visualizing Phylogenetic Networks
No full textWe study the problem of visualizing phylogenetic networks, which are extensions of the Tree of Life in biology. We use a space filling visualization method, called DAGmaps, in order to obtain clear visualizations using limited space. In this paper, we restrict our attention to galled trees and galled networks and present linear time algorithms for visualizing them as DAGmaps
Low Ply Drawings of Trees
No full textWe consider the recently introduced model of low ply graph drawing, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribution of the vertices in the plane. The ply-disk of a vertex in a straight-line drawing is the disk centered at it whose radius is half the length of its longest incident edge. The largest number of ply-disks having a common overlap is called the ply-number of the drawing.
We focus on trees. We first consider drawings of trees with constant ply-number, proving that they may require exponential area, even for stars, and that they may not even exist for bounded-degree trees. Then, we turn our attention to drawings with logarithmic ply-number and show that trees with maximum degree 6 always admit such drawings in polynomial area
Obstructing Visibilities with One Obstacle
No full textObstacle representations of graphs have been investigated quite intensely over the last few years. We focus on graphs that can be represented by a single obstacle. Given a (topologically open) non-self-intersecting polygon C and a finite set P of points in general position in the complement of C, the visibility graph GC(P) has a vertex for each point in P and an edge pq for any two points p and q in P that can see each other, that is, pq¯∩C=∅. We draw GC(P) straight-line and call this a visibility drawing. Given a graph G, we want to compute an obstacle representation of G, that is, an obstacle C and a set of points P such that G=GC(P). The complexity of this problem is open, even when the points are exactly the vertices of a simple polygon and the obstacle is the complement of the polygon—the simple-polygon visibility graph problem.
There are two types of obstacles; outside obstacles lie in the unbounded component of the visibility drawing, whereas inside obstacles lie in the complement of the unbounded component. We show that the class of graphs with an inside-obstacle representation is incomparable with the class of graphs that have an outside-obstacle representation. We further show that any graph with at most seven vertices has an outside-obstacle representation, which does not hold for a specific graph with eight vertices. Finally, we show NP-hardness of the outside-obstacle graph sandwich problem: given graphs G and H on the same vertex set, is there a graph K such that G⊆K⊆H
and K has an outside-obstacle representation. Our proof also shows that the simple-polygon visibility graph sandwich problem, the inside-obstacle graph sandwich problem, and the single-obstacle graph sandwich problem are all NP-hard
A Direct Proof of the Strong Hanani–Tutte Theorem on the Projective Plane
No full textWe reprove the strong Hanani–Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely on the characterization of forbidden minors, which gives hope to extend it to other surfaces. Moreover, our approach can be used to provide an efficient algorithm turning a Hanani–Tutte drawing on the projective plane into an embedding
Track Layout Is Hard
No full textWe show that testing whether a given graph has a 3-track layout is hard, by characterizing the bipartite 3-track graphs in terms of leveled planarity. Additionally, we investigate the parameterized complexity of track layouts, showing that past methods used for book layouts do not work to parameterize the problem by treewidth or almost-tree number but that the problem is (non-uniformly) fixed-parameter tractable for tree-depth. We also provide several natural classes of bipartite planar graphs, including the bipartite outerplanar graphs, squaregraphs, and dual graphs of arrangements of monotone curves, that always have 3-track layouts
Simultaneous Orthogonal Planarity
No full textWe introduce and study the ORTHOSEFE-k problem: Given k planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the k graphs? We show that the problem is NP-complete for k≥3 even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for k≥2 even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for k=2 when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge
Monotone Simultaneous Embeddings of Paths in d Dimensions
No full textWe study the following problem: Given k paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that, for any dimension d, there is a set of d+1 paths that does not admit a monotone simultaneous geometric embedding