Red/Red-maximal augmentation
Red Augmentation
- Red edges: Have no crossings
- A red augmentation only adds red edges.
- Definition from Eades et al.:
"A red augmentation G′ = (V, E′) of G = (V, E) is a 1-plane graph with E ⊆ E′ such that no edge in E′ − E has a crossing"
Red-maximal augmentation
Definition: 1-planar graph is red-maximal if no more red edges can be added, the addition of any edge would create a crossing. (Denoted as G+)
Properties of red-maximal graphs:
- Every face of planarization is a simple cycle
- Every cross induces a 4-clique
- Internal faces with no crossing vertex are 3-cycles
- Internal faces with a crossing vertex can be 3,4, or 5 cycles.
- The outer face has no crossing vertices
- The outer face is either a 3, or 4 cycle.
These properties are important in simplifying the drawing step of the proof. Illustrations of the various proofs for the properties are below.
Property 2
There is exactly one face in G*(planarization of a red-maximal 1-plane graph) where 2 nonadjacent vertices, (A, B) above for example, and a crossing vertex (𝛾) occur consecutively. You can connect these two non-crossing vertices.
Important Property of Internal Faces
For two nonconsecutive, non-crossing vertices on an internal face F, there must be an edge between the two outside of F.
- If this edge (purple above) did not exist, then an edge inside F (gray dotted) must exist to maintain red-maximality.
Property 3
What does this tell us?
No internal face of G* has more than 4 non-crossing vertices (vertices in G+)
Property 3: If an internal face of has no crossing vertices, it can consist of 3 vertices at most. (for cases of 4 vertices see figure above, a "bad K4" graph is constructed, containing the bulgari subgraph)
(A face made up of 5 or more vertices cannot be red-maximal, there will be 2 crossings)
Property 4
First: Prove that there cannot be an internal face with more than 1 crossing vertex.
For the proof's purpose we consider an internal face F made up of 2 crossing vertices. At least 2 existent nodes in the red-maximal graph (red dots) must exist. An example is shown to the left.
Property 4 (cont.)
Using the important property of internal faces from above, there must be an edge between the 1-2 possible sets of nonconsecutive vertices outside of F. This must be from the edges forming the 2 crossing vertices. Any edge that may exist besides that is bound to cross an exterior face twice or the crossing edges themselves.
- Property 4: there can only exist 1 crossing vertex per internal face, and at most 4 non-crossing vertices.
Property 5:
No crossings are permitted on the outer face since it would induce the "bad K4" graph and subsequently the bulgari subgraph as seen in the section for Property 3
Property 6:
Using the same reasoning as property 4, since there cannot exist a crossing on the outer face the outer face can be a 3-cycle or a 4-cycle at most. If a 4-cycle exists on the outer face, it will induce a clique about a crossing (Property 2).