- If the graph is disconnected, we can sort the point set by angle with some outside point (that is not in the point set), partition the point set appropriately, and embed the graph's connected components in the partitions of the point set.

- If the graph is connected but has a cutvertex v, we can sort the point set by angle with some point p, partition the point set (excluding an extreme point p) appropriately, and embed the cut components of in the partitions, joining them at p.

Let's consider one final reduction. Suppose we can embed *maximal* outer-planar graphs efficiently (that is, no edges can be added inside to the graph if it is to remain outer-planar). Then given any outer-planar graph, we can add edges to it until it is maximal, embed the resulting maximal graph, then remove all added edges from the embedding. Again, this modification can be done in

The difficult part, then, is embedding maximal 2-connected outer-planar graphs efficiently. To do this, we will use something called an (r,s)-triangle, the key to finding our embeddings. From here on in, we will assume our outer-planar graphs are maximal and 2-connected.

Note that in a maximal outer-planar graph, each bounded face is a triangle. Note also that in a 2-connected outer-planar graph, the unbounded face is a cycle since it contains no cutvertices. This means that a straight-line embedding of a maximal outer-planar graph is equivalent to a triangulation of a polygon on the point set.

In an outer-planar graph (remember, each bounded face is a triangle since we assume the graph is maximal), an (r,s)-triangle is a face in the graph with at least one edge on the unbounded face such that deleting the vertices of the triangle cuts the graph into two outer-planar graphs of size r and s. Note that r and s must be non-negative, and r+s = n-3.

In this example, every triangle with an edge on the outer face is shown, along with its corresponding values of r and s.

In a point set, an (r,s)-triangle is a triangle Δabc such that the following hold:

- a and b both lie on the point set's convex hull.
- The interior of Δabc contains no other point in the point.
- There is a line that passes through both c and the line ab such that excluding a, b, and c, r points are on the "right" side of the line and s points are on the other side of the line.

In this example, the triangle shown is a (7,0)-triangle, a (6,1)-triangle, a (5,2)-triangle, a (4,3)-triangle, and a (3,4)-triangle. Unlike (r,s)-triangles in graphs, a single triangle in a point set can be an (r,s)-triangle for several different values of r and s.