Augmentation Step

Overview

Goal: Construct red-maximal augmentation

1. Add edges around each crossing to surround with a 4-cycle.

2. Triangulate remaining faces.

Proof

Possible cases when adding edge surrounding crossing

1.No bulgari graph

This is what we are looking for

2. Bulgari graph exists

This alternative edge (a,b) can be added with a naïve algorithm

3. Must avoid somehow

Even if Case 1 is found, a bulgari graph can still be formed with another crossing vertex

Cases 1 and 2 are simple to distinguish. If the crossing vertex (𝛾) is clockwise with respect to vertices A and B, a bulgari graph will be created if the cycle (A, B, 𝛾) is anti-clockwise and vice-versa.

To prevent case 3 from ocurring, a stronger proposition is made:

  • For every pair of non adjacent vertices (x,y) that share at least 1incident crossing vertex, there is crossing vertex such that an edge can be added in the form of case 1 above

Proof: For a collection of crossing edges for 2 non-adjacent vertices (x,y) (Fig(A)), there must be a particular crossing vertex, clockwise to vertices (x,y), where all previous crossing vertices (in circular order) are anti-clockwise. If there were to exist a clockwise crossing vertex after this point, it would imply the existence of a gucci subgraph and vice-versa. This is illustrated below.

Crossing Edges for (x,y)

Fig(A)

Forbidden Case

Fig(B)

Here an anti-clockwise crossing vertex appears amongst anticlockwise (boxed). The gucci subgraph formed is highlighted to the right.

Fig(C)

The gucci subgraph is highlighted in purple

Importance

Since we know such a crossing vertex as the one boxed to the left can't exist, it is possible to add edges around crossing vertices as mentioned before to surround each with a 4 cycle. As shown in the drawing the the left, this prevents the formation of a bulgari or gucci subgraph.

This proves the first step is possible, surrounding every crossing vertex with a 4-cycle, as Case 3 shown above is not possible.

STEP 2: Triangulation

Once every crossing has been surrounded by a 4 cycle, any non-adjacent vertices (x,y) that share a face F in the graph can be connected with edge (x,y) inside F without crossings, maintaining a red augmentation.

Now the red-maximal augmentation is complete.

Time Complexity