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.

Google Sites

Report abuse