On making a graph crossing-critical

Abstract

A graph is crossing-critical if its crossing number decreases when we remove any of its edges. Recently it was proved that if a non-planar graph G is obtained by adding an edge to a cubic polyhedral (planar 3-connected) graph, then G can be made crossingcritical by a suitable multiplication of its edges. Here we show: (i) a new family of graphs that can be transformed into crossing-critical graphs by a suitable multiplication of its edges, and (ii) a family of graphs that cannot be made crossing-critical by any multiplication of its edges.