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)

This is a drawing of an internal face F with 4 non-crossing vertices. We know from Property 3 above that this is as many 'real vertices' we can have. In the drawing to the right we see F with only 2 non-crossing vertices.

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).

Google Sites

Report abuse