Extending Simple Drawings Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Leviu0027s enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NPcomplete. Moreover, we show that the maximization version of the problem is APXhard. We also present a polynomialtime algorithm for deciding whether one edge uv can be inserted into D(G) when u,v is a dominating set for the graph G.

On the Edgelength Ratio of Outerplanar Graphs We show that any outerplanar graph admits a planar straightline drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any (epsilon u003e 0) there are outerplanar graphs that cannot be drawn with an edgelength ratio smaller than (2  epsilon ). We also show that every bipartite outerplanar graph has a planar straightline drawing with edgelength ratio 1, and that, for any (k ge 1), there exists an outerplanar graph with a given combinatorial embedding such that any planar straightline drawing has edgelength ratio greater than k.