<p>One way to augmenting an embedded planar graph (i.e. a plane graph) to become biconnected, while preserving the embedding, is</p>

<pre>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</pre>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-05-16T06:11:03.090Z
There is a polynomial time algorithm for this problem:
UGMENTATION PROBLEMS*
KAPALI P. ESWARAN’I AND\ R. ENDRE TARJAN
http://epubs.siam.org/doi/abs/10.1137/0205044
Sariel Har-Peled
CC BY-SA 3.0
2017-05-07T06:00:02.940Z
2017-05-07T06:49:16.177Z
2017-05-07T06:49:16.177Z
David Eppstein
<p>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?</p>

<p>Few more notes:</p>

<ul>
<li>By biconnected I mean no single cut vertex and no bridge,</li>
<li>We cannot change given embedding,</li>
<li>We do not have to minimize number of edges added</li>
</ul>

CC BY-SA 3.0
2017-05-06T19:09:47.260Z
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?
daniello
CC BY-SA 3.0
2017-05-06T19:25:05.167Z
I've editted my post.
tomwesolowski
CC BY-SA 3.0
2017-05-06T19:48:50.770Z
If one does not have to minimize the number of edges added, then why not just triangulate the plane graph?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2017-05-06T20:09:08.507Z
That's what I try to do :). Doesn't the algorithm require biconnected planar graph?
tomwesolowski
CC BY-SA 3.0
2017-05-06T21:16:34.813Z
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](https://cms.math.ca/10.4153/CJM-1963-029-x), 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.
Noam Zeilberger
CC BY-SA 3.0
2017-05-06T21:42:26.767Z
"any bridge contains a pair of cut vertices" that's not true.
tomwesolowski
CC BY-SA 3.0
2017-05-06T21:52:49.080Z
According to Wiki: "A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates more components than previously in the graph." Why does any loop contain a cut vertex?
tomwesolowski
CC BY-SA 3.0
2017-05-07T08:41:14.580Z
@Tomek the definition of a cut vertex in a planar map (= plane graph) from Tutte's paper is slightly different. It excludes bridges and loops, except for the very special case of the two one-edge maps. If you are only considering simple graphs (i.e., no loops or multiple edges), though, then this is not an issue.
Noam Zeilberger
<planar-graphs>
Making planar graph biconnected
tomwesolowski
# Making planar graph biconnected

(Asked by: username_0 on 2017-05-06)

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

**Tags:** planar-graphs
> **Comments:**
> **username_1**: 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?  
> **username_0**: I've editted my post.  
> **username_2**: If one does not have to minimize the number of edges added, then why not just triangulate the plane graph?  
> **username_0**: That's what I try to do :). Doesn't the algorithm require biconnected planar graph?  
> **username_3**: 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](https://cms.math.ca/10.4153/CJM-1963-029-x), 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.  
> **username_0**: "any bridge contains a pair of cut vertices" that's not true.  
> **username_0**: According to Wiki: "A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates more components than previously in the graph." Why does any loop contain a cut vertex?  
> **username_3**: @Tomek the definition of a cut vertex in a planar map (= plane graph) from Tutte's paper is slightly different. It excludes bridges and loops, except for the very special case of the two one-edge maps. If you are only considering simple graphs (i.e., no loops or multiple edges), though, then this is not an issue.  

---

## 1 answers

### Answer by username_4 on 2017-05-07. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_5**: There is a polynomial time algorithm for this problem: UGMENTATION PROBLEMS* KAPALI P. ESWARAN’I AND\ R. ENDRE TARJAN http://epubs.siam.org/doi/abs/10.1137/0205044  

---

