Non-planar core reduction of graphs (Q1011763)

An algorithm is presented for reducing the number of edges of a graph while keeping the four main non-planarity characteristics of the original graph; its crossing number, skewness, coarseness and thickness (three of which are known to yield NP-hard optimization problems). This is intended as a means of speeding up the computation of these characteristics for heuristics and exact algorithms whose computational complexity depends of the number of the edges of the graph. The authors claim the experimental average reduction of 45\% of the number of edges of the original graph. The results rely on the use of the SPQR-trees, representing the decomposition of \(2\)-connected graphs into triconnected components. The definition of the non-planar core using maximal planar \(2\)-components is followed by a pseudocode for computing the core for non-planar graphs. The algorithm is shown to be of linear time complexity and to preserve all the four above listed non-planarity characteristics. The paper concludes with a discussion of further possible improvements, and the results of tests performed on the benchmark family known as the Rome library.