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 Reduced Height
No full textA straight-line (respectively, polyline) drawing Γ of a planar graph G on a set L k of k parallel lines is a planar drawing that maps each vertex of G to a distinct point on L k and each edge of G to a straight line segment (respectively, a polygonal chain with the bends on L k ) between its endpoints. The height of Γ is k, i.e., the number of lines used in the drawing. In this paper we compute new upper bounds on the height of polyline drawings of planar graphs using planar separators. Specifically, we show that every n-vertex planar graph with maximum degree Δ, having a simple cycle separator of size λ, admits a polyline drawing with height 4n/9 + O(λΔ), where the previously best known bound was 2n/3. Since λ∈O(n√) , this implies the existence of a drawing of height at most 4n/9 + o(n) for any planar triangulation with Δ∈o(n√) . For n-vertex planar 3-trees, we compute straight-line drawings with height 4n/9 + O(1), which improves the previously best known upper bound of n/2. All these results can be viewed as an initial step towards compact drawings of planar triangulations via choosing a suitable embedding of the input graph
Clustered Planarity Testing Revisited
No full textThe Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible.
We also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm
On Monotone Drawings of Trees
No full textA crossing-free straight-line drawing of a graph is monotone if there is a monotone path between any pair of vertices with respect to some direction. We show how to construct a monotone drawing of a tree with n vertices on an O(n 1.5) ×O(n 1.5) grid whose angles are close to the best possible angular resolution. Our drawings are convex, that is, if every edge to a leaf is substituted by a ray, the (unbounded) faces form convex regions. It is known that convex drawings are monotone and, in the case of trees, also crossing-free.
A monotone drawing is strongly monotone if, for every pair of vertices, the direction that witnesses the monotonicity comes from the vector that connects the two vertices. We show that every tree admits a strongly monotone drawing. For biconnected outerplanar graphs, this is easy to see. On the other hand, we present a simply-connected graph that does not have a strongly monotone drawing in any embedding
Circular Tree Drawing by Simulating Network Synchronisation Dynamics and Scaling
No full textWe present an algorithm which produces circular-shape layouts of trees by simulating synchronisation dynamics on the tree. Our approach consists of evolving scalar dynamical values assigned to the nodes. Then the dissimilarities between the values of each pair of nodes are utilised to calculate the coordinates of the nodes by using a lower bound on dissimilarities and scaling up the lower bound per iteration
Fan-Planar Graphs: Combinatorial Properties and Complexity Results
No full textIn a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt, who proved that every n-vertex fan-planar drawing has at most 5n − 10 edges, and that this bound is tight for n ≥ 20. We extend their result from both the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrained versions of fan-planar drawings and study the relationship between fan-planarity and k-planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete
On the Complexity of HV-rectilinear Planarity Testing
No full textAn HV-restricted planar graph G is a planar graph with vertex-degree at most four and such that each edge is labeled either H (horizontal) or V (vertical). The HV-rectilinear planarity testing problem asks whether G admits a planar drawing where every edge labeled V is drawn as a vertical segment and every edge labeled H is drawn as a horizontal segment. We prove that HV-rectilinear planarity testing is NP-complete even for graphs having vertex degree at most three, which solves an open problem posed by both Manuch et al. (GD 2010) and Durucher et al. (LATIN 2014). We also show that HV-rectilinear planarity can be tested in polynomial time for partial 2-trees of maximum degree four, which extends a previous result by Durucher et al. (LATIN 2014) about HV-restricted planarity testing of biconnected outerplanar graphs of maximum degree three. When the test is positive, our algorithm returns an orthogonal representation of G that satisfies the given H- and V-labels on the edges
Circle-Representations of Simple 4-Regular Planar Graphs
No full textLovász conjectured that every connected 4-regular planar graph G admits a realization as a system of circles, i.e., it can be drawn on the plane utilizing a set of circles, such that the vertices of G correspond to the intersection and touching points of the circles and the edges of G are the arc segments among pairs of intersection and touching points of the circles. In this paper, (a) we affirmatively answer Lovász's conjecture, if G is 3-connected, and, (b) we demonstrate an infinite class of connected 4-regular planar graphs which are not 3-connected and do not admit a realization as a system of circles
Smooth Orthogonal Layouts
No full textWe study the problem of creating smooth orthogonal layouts for planar graphs. While in traditional orthogonal layouts every edge is made of a sequence of axis-aligned line segments, in smooth orthogonal layouts every edge is made of axis-aligned segments and circular arcs with common tangents. Our goal is to create such layouts with low edge complexity, measured by the number of line and circular arc segments. We show that every biconnected 4-planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity-2 traditional orthogonal layout, we can transform it into a smooth complexity-2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity-2 layout