Planarization

In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.^[1][2]

Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial vertex, causing each crossed edge to be subdivided into a path. The original graph will be represented as an immersion minor of its planarization.

In incremental planarization, the planarization process is split into two stages. First, a large planar subgraph is found within the given graph. Then, the remaining edges that are not already part of this subgraph are added back one at a time, and routed through an embedding of the planar subgraph. When one of these edges crosses an already-embedded edge, the two edges that cross are replaced by two-edge paths, with a new artificial vertex that represents the crossing point placed at the middle of both paths.^[1][2] In some case a third local optimization stage is added to the planarization process, in which edges with many crossings are removed and re-added in an attempt to improve the planarization.^[1]

Finding the largest planar subgraph

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]

Adding edges to a planarization

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]

References

1. Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael; Mutzel, Petra (2014), "Crossings and planarization", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, Florida.
2. Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs (1st ed.), Prentice Hall, pp. 215–218, ISBN 0133016153.
3. Chimani, Markus (2008), Computing Crossing Numbers (PDF), Ph.D. dissertation, Technical University of Dortmund, Section 4.3.1, archived from the original (PDF) on 2015-11-16.
4. Călinescu, Gruia; Fernandes, Cristina G.; Finkler, Ulrich; Karloff, Howard (1998), "A better approximation algorithm for finding planar subgraphs", Journal of Algorithms, 27 (2): 269–302, CiteSeerX 10.1.1.37.4317, doi:10.1006/jagm.1997.0920, MR 1622397, S2CID 8329680.
5. Kawarabayashi, Ken-ichi; Reed, Bruce (2007), "Computing crossing number in linear time", Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC '07), pp. 382–390, doi:10.1145/1250790.1250848, MR 2402463, S2CID 13000831.
6. Jünger, M.; Mutzel, P. (1996), "Maximum planar subgraphs and nice embeddings: practical layout tools" (PDF), Algorithmica, 16 (1): 33–59, doi:10.1007/s004539900036, MR 1394493.
7. Weisstein, Eric W. "Graph Skewness". MathWorld.
8. Kawarabayashi, Ken-ichi (2009), "Planarity allowing few error vertices in linear time", 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09) (PDF), pp. 639–648, doi:10.1109/FOCS.2009.45, MR 2648441, S2CID 11647021.
9. Edwards, Keith; Farr, Graham (2002), "An algorithm for finding large induced planar subgraphs", Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Comp. Sci., vol. 2265, Springer, pp. 75–80, doi:10.1007/3-540-45848-4_6, MR 1962420.
10. Gutwenger, Carsten; Mutzel, Petra; Weiskircher, René (2005), "Inserting an edge into a planar graph", Algorithmica, 41 (4): 289–308, doi:10.1007/s00453-004-1128-8, MR 2122529, S2CID 6441726.