On the Pair-Crossing Number
Pável Valtr · 2005
1. Introduction By a drawing of a graph G , we mean a drawing in the plane such that vertices are represented by distinct points and edges by arcs. The arcs are allowed to cross, but they may not pass through vertices (except for their endpoints) and no point is an internal point of three or more arcs. Two arcs may have only finitely many common points. A crossing is a common internal point of two arcs. A crossing pair is a pair of edges which cross each other at least once. A drawing is planar, if there are no crossings in it. A subdrawing of a drawing is defined analogously as a subgraph of a graph. The crossing number cr( G ) of a graph G is the minimum possible number of crossings in a drawing of G. The pair-crossing number pair-cr( G ) of G is the minimum possible number of (unordered) crossing pairs in a drawing of G. In this paper we investigate the relation between the crossing number and the pair-crossing number. Clearly, pair-cr( G ) ≤ cr( G ) holds for any graph G. The problem of deciding whether cr( G ) = pair-cr( G ) holds for every G appears quite challenging. Let f ( k ) be the maximum cr( G ), taken over all graphs G with pair-cr( G ) = k. Obviously, f(k) ≥ k. Pach and Toth [2000] proved that f ( k ) ≤ 2 k 2 . In fact, they proved this bound in a stronger version when the pair-crossing number is replaced by the so-called odd-crossing number, which is the minimum number of pairs of edges in a drawing that cross each other an odd number of times.