Planarization

Using incremental planarization for graph drawing is most effective when the first step of the process finds as large a planar graph as possible. Unfortunately, finding the planar subgraph with the maximum possible number of edges (the maximum planar subgraph problem^[3]) is NP-hard, and MaxSNP-hard, implying that there probably does not exist a polynomial time algorithm that solves the problem exactly or that approximates it arbitrarily well.^[4]

In an n-vertex connected graph, the largest planar subgraph has at most 3n − 6 edges, and any spanning tree forms a planar subgraph with n − 1 edges. Thus, it is easy to approximate the maximum planar subgraph within an approximation ratio of one-third, simply by finding a spanning tree. A better approximation ratio, 9/4, is known, based on a method for finding a large partial 2-tree as a subgraph of the given graph.^[1][4] Alternatively, if it is expected that the planar subgraph will include almost all of the edges of the given graph, leaving only a small number k of non-planar edges for the incremental planarization process, then one can solve the problem exactly by using a fixed-parameter tractable algorithm whose running time is linear in the graph size but non-polynomial in the parameter k.^[5] The problem may also be solved exactly by a branch and cut algorithm, with no guarantees on running time, but with good performance in practice.^[1][6] This parameter k is known as the skewness of the graph.^[3][7]

There has also been some study of a related problem, finding the largest planar induced subgraph of a given graph. Again, this is NP-hard, but fixed-parameter tractable when all but a few vertices belong to the induced subgraph.^[8] Edwards & Farr (2002) proved a tight bound of 3n/(Δ + 1) on the size of the largest planar induced subgraph, as a function of n, the number of vertices in the given graph, and Δ, its maximum degree; their proof leads to a polynomial time algorithm for finding an induced subgraph of this size.^[9]

Once a large planar subgraph has been found, the incremental planarization process continues by considering the remaining edges one by one. As it does so, it maintains a planarization of the subgraph formed by the edges that have already been considered. It adds each new edge to a planar embedding of this subgraph, forming a drawing with crossings, and then replaces each crossing point with a new artificial vertex subdividing the two edges that cross.^[1][2] In some versions of this procedure, the order for adding edges is arbitrary, but it is also possible to choose the ordering to be a random permutation, running the same algorithm several times and returning the best planarization that it finds.^[1]

In the simplest form of this process, the planar embedding of the planarized subgraph is not allowed to change while new edges are added. In order to add each new edge in a way that minimizes the number of crossings it forms, one can use a shortest path algorithm in the dual graph of the current embedding, in order to find the shortest sequence of faces of the embedding and edges to be crossed that connects the endpoints of the new edge to each other. This process takes polynomial time per edge.^[2]

Fixing the embedding of the planarized subgraph is not necessarily optimal in terms of the number of crossings that result. In fact, there exist graphs that are formed by adding one edge to a planar subgraph, where the optimal drawing has only two crossings but where fixing the planar embedding of the subgraph forces a linear number of crossings to be created.^[1] As a compromise between finding the optimal planarization of a planar subgraph plus one edge, and keeping a fixed embedding, it is possible to search over all embeddings of the planarized subgraph and find the one that minimizes the number of crossings formed by the new edge.^[1][10]