Search

This paper starts the investigation of a constrained version of the point-set embed-dability problem. Let G = (V,E) be a planar graph with n vertices, G′ = (V′,E′) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: • If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E\E′ have at most 4 bends each. • If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E\E′ is at most 8. • If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E \ E′ is O(2k). [ABSTRACT FROM AUTHOR]

We establish new results on the curve complexity of k -colored point-set embeddings when k = 3. We show that there exist 3-colored caterpillars with only three independent edges whose 3-colored point-set embeddings may require Ω (n 1 3 ) bends on Ω (n 2 3 ) edges. This settles an open problem by Badent et al. [5] about the curve complexity of point set embeddings of k -colored trees and it extends a lower bound by Pach and Wenger [35] to the case that the graph only has O (1) independent edges. Concerning upper bounds, we prove that any 3-colored path admits a 3-colored point-set embedding with curve complexity at most 4. In addition, we introduce a variant of the k -colored simultaneous embeddability problem and study its relationship with the k -colored point-set embeddability problem. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of . We concentrate on trees and show how to compute the output in time in a real-RAM model and with at most edges with at most bends, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least bends on edges. [Copyright &y& Elsevier]

Abstract: Let be a planar graph with vertices and with a partition of the vertex set into subsets for some positive integer . Let be a set of distinct points in the plane with a partition into subsets with (). This paper studies the problem of computing a planar polyline drawing of , such that each vertex of is mapped to a distinct point of . Lower and upper bounds on the number of bends per edge are proved for any . In the special case , we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717–728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest. [Copyright &y& Elsevier]

Let C be the family of 2D curves described by concave functions, let G be a planar graph, and let L be a linear ordering of the vertices of G. L is a curve embedding of G if for any given curve Λ∈C there exists a planar drawing of G such that: (i) the vertices are constrained to be on Λ with the same ordering as in L, 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. [Copyright &y& Elsevier]

Abstract: In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position. [Copyright &y& Elsevier]