An algorithm for delta-wye reduction of almost-planar graphs

摘要

A nonplanar graph G is almost-planar if, for every edge e of G, either Ge or G/e is planar. The class of almost-planar graphs were introduced in 1990 by Gubser. In 2015, Wagner proved that every almost-planar graph is delta-wye reducible to K-3,K-3. Moreover, he showed that there exists a reduction sequence in which every graph is almost-planar. We obtain an O(n(2)) algorithm for Wagner's result. We also prove that simple, 3-connected, almost-planar graphs have crossing number one and furthermore that these graphs are 3-terminal delta-wye reducible to K-6 minus the edges of a triangle, whose vertices are taken as terminals. (C) 2020 Published by Elsevier B.V.