Local Crossing Number

The local crossing number is defined as the least nonnegative integer such that the graph has a -planar drawing. In other words, it is the smallest possible number of times that a single edge in a graph is crossed over all possible graph drawings. Guy et al. (1968) attribute the definition to unpublished work of Ringel.

The local crossing number of a graph is called the cross-index by Thomassen (1988) and sometimes also the crossing parameter (Schaefer 2013), but Schaefer (2013) strongly encourages the use of "local crossing number." However, the term "planarity" might be more more descriptive and more concise.

Schaefer (2014) and Ábrego and Fernández-Merchant (2017) denote the local crossing number of a graph as .

It follows from Brooks' theorem that graph thickness is at most one plus the local crossing number (Kainen 1973, Thomassen 1988).

Graphs with local crossing number 0 are equivalent to planar graphs. In general, a k-planar graph can have local crossing number 0, 1, ..., or .

Since the Heawood graph and complete graph are nonplanar but, as illustrated above, have embeddings with local crossing number 1, they are 1-planar.

Classes of graphs with local crossing number 1 (i.e., graphs that are 1-planar without being planar) include the king graphs and Lindgren-Sousselier graphs.

The crossed dodecahedral graph has local crossing number 2.

The best known bound on the graph crossing number of the complete graph (De Klerk et al. 2007) gives a local crossing number bound of

(Ábrego and Fernández-Merchant 2017).

The version of local crossing number restricted to straight-line edges is known as the rectilinear local crossing number.