Making planar graph biconnected I've given a planar graph (with clockwise ordering of vertices). I would like to make it biconnected by adding some number of edges. Graph should remain planar, of course. How can I do this?

Few more notes:


By biconnected I mean no single cut vertex and no bridge,
We cannot change given embedding,
We do not have to minimize number of edges added
One way to augmenting an embedded planar graph (i.e. a plane graph) to become biconnected, while preserving the embedding, is

for each articulation vertex v:
  for each two edges vu and vw that are consecutive in the cyclic order around v:
    if u and w belong to different biconnected components of G:
      add edge uw

You have to be a little careful about the ordering of operations, though, because if you did this simultaneously at both endpoints of a bridge edge you could create a non-planarity. You have to do them one at a time.

This method can add significantly fewer edges than triangulation: each new edge reduces the number of biconnected components by one, so the total number of edges added is less than the original number of biconnected components.