We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph problem---to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph---and the simultaneous planarity problem---to find planar drawings of two graphs that coincide on shared vertices and edges. In both cases we show that if the required planar drawings exist, then there are planar drawings with a linear number of bends per edge and, in the case of simultaneous planarity, a constant number of crossings between every pair of edges. Our proofs provide efficient algorithms if the combinatorial embedding of the drawing is given. Our result on partially embedded graph drawing generalizes a classic result by Pach and Wenger which shows that any planar graph can be drawn with a linear number of bends per edge if the location of each vertex is fixed.
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 G^'@?G on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of G^'. We concentrate on trees and show how to compute the output in O(n^2logn) time in a real-RAM model and with at most n-k edges with at most [email protected]?k [email protected]? 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 k-3 bends on n-k edges.