Goal: Construct red-maximal augmentation
1. Add edges around each crossing to surround with a 4-cycle.
2. Triangulate remaining faces.
Proof
This is what we are looking for
This alternative edge (a,b) can be added with a naïve algorithm
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:
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.
Fig(A)
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
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.
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.