Tóth, Géza


Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

Problem   Does the following equality hold for every graph $ G $? \[ \text{pair-cr}(G) = \text{cr}(G) \]

The crossing number $ \text{cr}(G) $ of a graph $ G $ is the minimum number of edge crossings in any drawing of $ G $ in the plane. In the pairwise crossing number $ \text{pair-cr}(G) $, we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

Syndicate content