# 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
• Biconnected = no single vertex cut or no single edge cut? Are you trying to minimize the number of added edges, or just adding any set of edges as long as the graph stays planar? Should the new edges respect the given embedding, or can we change the embedding as long as the graph stays planar? May 6 '17 at 19:09
• I've editted my post. May 6 '17 at 19:25
• If one does not have to minimize the number of edges added, then why not just triangulate the plane graph? May 6 '17 at 19:48
• That's what I try to do :). Doesn't the algorithm require biconnected planar graph? May 6 '17 at 20:09
• First, a couple comments: 1. any bridge contains a pair of cut vertices, so the condition "no cut vertices and no bridges" is redundant; 2. a planar map with no cut vertex is called non-separable (see the intro to Section 6 of this paper, as well as Figure 4 for a list of small non-separable planar maps). Second, are we allowed to also add vertices? If not, then I think this is impossible, because any loop contains a cut vertex, and you cannot get rid of a loop by just adding edges. May 6 '17 at 21:16

for each articulation vertex v:
add edge uw