Drawing Step
Straight-line drawing
Input: red-maximal augmentation of a 1-plane graph without forbidden subgraphs. (From augmentation step)
Algorithm:
- Remove crossing edges
- Construct SPR tree from the resulting planar subgraph
- Replace virtual edges with convex drawing of children
The SPR tree can be constructed in linear time, as well as the convex drawings of each child via an algorithm given by Chiba et al.. Therefore the straight line drawing can be completed in linear time.
Combined with the linear time augmentation algorithm prior to this step, the overall algorithm has linear time complexity.
The SPR tree structure as well as the specific process is detailed further here.
Example Input:
Red-maximal augmentation
The input of our algorithm is a red-maximal augmentation provided by the previous step.
*green edges are crossing edges
Step 1. Planar subgraph
Crossing edges are first removed to produce a planar subgraph.
Root R-node
Blue edge indicates virtual edge
1. Left/Right Triangle
Here the virtual edge exists in the graph and constitutes a P-node as it is connected by 3 edges. Left and right triangles are defined as the convex polygons of its children, which are S-nodes. The final drawing is below.
2.Left/Right Trapezoid
In the case of there being two additional vertices than the graph pictured above, the P-node will determine left/right trapezoids for the convex polygons of its children which again are S-nodes. The final drawing is below
3. Rhombus
If the virtual edge did not exist in the original graph and was introduced during tree decomposition, a rhombus shape is chosen by the virtual P-node.
Note above: The blue dashed lines represent the virtual edge in each child. In case of the P-nodes the virtual edge is the solid black line, while the dashed lines indicate the children on either side of the virtual edge which are to be given a convex polygon.
Overview of possible children of the P-node above.
1. Left/Right Triangle(s)
One possibility is that the virtual edge exists creating a P-node. In cases such as the one illustrated above, the child of the P-node is an R-node with a 4-cycle as its outer face, creating a left and/or right triangle.
2. Trapezoid
In cases where there is a cycle and an S-node is used, then there will be a trapezoid.
3. Rhombus
In a case similar to the left/right triangles, if the virtual edge does not exist in the graph and only exists for decomposition, a rhombus will be constructed
Explanation of final graph
In the case illustrated, the virtual edge (drawn in blue) exists in the graph. Since there are more than 3 edges connecting the two vertices A and D, including the virtual edge, a P-node is contructed. As its children create triangles, they create S-nodes and are drawn as triangles. As in the case illustrated in B, the child S-nodes can be drawn as triangles. As we know from property 2, there can be at most 4 vertices on an internal face, previously a 4-clique about a crossing (removed prior to tree construction).
If the virtual edge were introduced during tree construction and does not exist in the red-maximal graph, then it is possible for a rhombus shape to be chosen, as shown to the left. It is important to note that a similar hexagonal polygon, with two trapezoids, may not exist as internal faces cannot exceed 4 vertices.
To the right is an example decomposition given in the paper by Eades et al. This SPR tree has an S-Root node rather than the R-root node in the example above. We see similar defining of polygons for each child of the root's child P-nodes. In this case trapezoids are selected for each, as shown by the polygons chosen in the leaf nodes.
The 3 images below show the root S-node, the insertion of the trapezoids and the internal crossing edges of the polygonal children are inserted. This is always possible while maintaining 1-planarity as crossing edges can be inserted into a convex polygon without creating a new crossing.