1,721,101 research outputs found
Upward Topological Book Embeddings of DAGs
No full textLet G be a directed acyclic graph. An upward (k, h)-topological book embedding of G is an upward book embedding on k pages of a subdivision of G where every edge is replaced by a path having at most h+2 vertices. In this extended abstract it is shown that every DAG with n vertices admits an upward (d +1, 2\lceil log_d \rceil n - 1)-topological book embedding, where d is any integer such that d \geq 2. The result extends to the upward case well-known theorems for topological book embeddings of undirected graphs
Orthogonal planarity testing of bounded treewidth graphs
No full textGiven a graph G and an integer b, ORTHOGONALPLANARITY is the problem of testing whether G admits a planar orthogonal drawing with at most b bends. ORTHOGONALPLANARITY is known to be NP-complete. We show that this problem belongs to the XP class when parameterized by treewidth. The proof exploits a fixed-parameter tractable approach that uses two more parameters besides treewidth, namely the natural parameter b and the number of vertices with degree at most two of G. Such approach is based on the new concept of sketched orthogonal representation, which synthetically describes a family of equivalent orthogonal drawings. The approach is general enough to be applicable to other related problems, namely HV-PLANARITY and FLEXDRAW. Also, in the special case of series-parallel graphs we obtain that both ORTHOGONALPLANARITY and HV-PLANARITY can be solved in O(n3logn) time, which improves on the previous O(n4) bounds for these two
Book Embeddability of Series-Parallel Digraphs
No full textIn this paper we deal with the problem of computing upward two-page book embeddings of
Two Terminal Series–Parallel (TTSP) digraphs, which are a subclass of series–parallel digraphs. An optimal
O(n) time and space algorithm to compute an upward two-page book embedding of a TTSP-digraph with n
vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n3) time and assumes that the
input series–parallel digraph does not have transitive edges. An application of this result to a computational
geometry problem is also discussed. More precisely, upward two-page book embeddings are used to deal with
the upward point-set embeddability problem, i.e., the problem of mapping planar digraphs onto a given set
of points in the plane so that all edges are monotonically increasing in a common direction. The equivalence
between upward two-page book embeddability and upward point-set embeddability with at most one bend per
edge on any given set of points is proved. An O(n log n)-time algorithm for computing an upward point-set
embedding with at most one bend per edge for TTSP-digraphs is presented
Curve-Constrained Drawings of Planar Graphs
No full textLet be the family of 2D curves described by concave
functions, let be a planar graph, and let be a linear
ordering of the vertices of . is a {\em curve embedding} of
if for any given curve there exists a
planar drawing of such that: (i) the vertices are constrained
to be on with the same ordering as in , and (ii)
the edges are polylines with at most one bend. Informally
speaking, a curve embedding can be regarded as a two-page book
embedding in which the spine is bent. Although deciding whether a
graph has a two-page book embedding is an NP-hard problem, in this
paper it is proven that every planar graph has a curve embedding
which can be computed in linear time. Applications of the concept
of curve embedding to upward drawability and point-set
embeddability problems are also presented
Switch-Regular Upward Planar Embeddings of Directed Trees
No full textUpward planar drawings of digraphs are crossing free drawings where all edges flow in the upward direction. The problem of deciding whether a digraph admits an upward planar drawing is called the upward planarity testing problem, and it has been widely studied in the literature. In this paper we investigate a new upward planarity testing problem, that is, deciding whether a digraph admits an upward planar drawing having some special topological properties: such a drawing is called switch-regular. Switch-regular upward planar drawings have practical algorithmic
impacts in several graph drawing applications. We provide characterizations for the class of directed trees that admit a switch-regular upward planar drawing. Based on these characterizations we describe an optimal linear-time testing and embedding algorithm
Computing Radial Drawings on the Minimum Number of Circles
No full textA radial drawing is a representation of a graph in which the vertices lie on concentric circles of finite radius. In this paper we study the problem of computing radial drawings of planar graphs by using the minimum number of concentric circles. We assume that the edges are drawn as straight-line segments and that co-circular vertices can be adjacent. It is proven that the problem can be solved in polynomial time. The solution
is based on a characterization of those graphs that admit a crossing-free straight-line radial drawing on k circles. For the graphs in this family, a linear time algorithm that computes a radial drawing on k circles is also presented
- …
