Straight-line Drawing of 1-Planar Graphs
Overview:
Defines a 1-planar graph that permits a straight-line drawing using forbidden subgraphs, much like Kuratowski's theorem. This is the first extension of Fáry's Theorem (1948) which stated that any planar graph may be drawn using only straight-line representations of edges.
The proof is conducted via linear time algorithm for creating a maximal augmentation and straight-line drawing for a 1-planar graph without the forbidden subgraphs.
The intention of this site is to provide a description of the proof/algorithm as well as to provide some additional visualizations. Hopefully it can be useful as an accompaniment to the paper.
Terms
1-planar graph: A graph in which each edge has 0 or 1 crossing.
A crossing can be clockwise or anti-clockwise with respect to two incident vertices.
- The crossing 𝛾 is clockwise with respect to (a,b)
- The crossing 𝛾 is anti-clockwise with respect to (c,d)
Crossing vertices (𝛾) are denoted by a black circle. Vertices illustrated as a red dot are vertices that exist in the original graph.
The planarization of a graph G (G*) inserts a crossing vertex at every crossing in order to maintain planarity
Forbidden Subgraphs
Bulgari Graph
1-plane graph with path length 3.
Of the 4 angles surrounding the crossing in this subgraph, the 3 internal vertices will have to remain incident to the same face, that is the face created by the endpoints of the vertical line above and the crossing. A straight line representation of the graph will be a triangle as it is a collection of 3 edges sharing an interior face (not the outer face). It is impossible to draw such a triangle while maintaining incidence of the three angles shown above.
Gucci Graph
1-plane graph with 2 paths of length 2
Similar reasoning can be used with the gucci graph by considering the angles about each crossing. All of the endpoints of each 2-cycle cannot be inside of the interior face with a straight-line drawing.