1
$\begingroup$

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
$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – daniello
    May 6 '17 at 19:09
  • $\begingroup$ I've editted my post. $\endgroup$ May 6 '17 at 19:25
  • 1
    $\begingroup$ If one does not have to minimize the number of edges added, then why not just triangulate the plane graph? $\endgroup$ May 6 '17 at 19:48
  • $\begingroup$ That's what I try to do :). Doesn't the algorithm require biconnected planar graph? $\endgroup$ May 6 '17 at 20:09
  • $\begingroup$ 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. $\endgroup$ May 6 '17 at 21:16
4
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.