Subthrackleable graphs and four-cycles (Q1322234)

A drawing of a graph in the plane maps vertices to points and edges to simple arcs connecting their endpoints such that adjacent edges share only their common endpoints and nonadjacent edges share at most one transversal crossing. The maximum number of edge crossings in such a drawing is bounded above by the number of unordered pairs of nonadjacent edges. A graph is thrackled if it is drawn to achieve this bound. Not every graph can be thrackled. The Thrackle Conjecture is that the number of edges cannot exceed the number of vertices. But even this is not enough; the 4-cycle cannot be thrackled. Using this fact, the authors give a new upper bound on the maximum number of crossings in a drawing. This bound is the number of pairs of nonadjacent edges, minus the number of 4-cycles, plus the number of \(K_ 4\) subgraphs. They call a graph subthrackleable if it can be drawn to achieve this new bound. The authors give a number of graphs which cannot be thrackled but which can be subthrackled. They also give a large number of graphs which cannot be subthrackled. Both classes include examples with an arbitrarily large number of 4-cycles. The authors pay particular attention to cubes.