All Separating Triangles i na Plane Graph Can Be Optimally 'Broken' in Polynomial Time

摘要

Lai and Leinwand have shown that an arbitrary plane (i.e., embedded planar) graph G can be transformed, by adding crossover vertices, into a new plane graph G' admitting a rectangular dual. Moreover, they conjectured that finding a minimum set of such crossove vertices is an NP-complete problem. In this paper it is shown that the above problem can be resolved in polynomial time by reducing it to a graph covering problem, and an efficient algorithm for finding a minimum set of edges on which to insert the crossover vertices is also presented.