# 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, 2017 at 19:09
• I've editted my post. May 6, 2017 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, 2017 at 19:48
• That's what I try to do :). Doesn't the algorithm require biconnected planar graph? May 6, 2017 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, 2017 at 21:16

for each articulation vertex v:
add edge uw