Local Crossing Number

The local crossing number is defined as the least nonnegative integer k such that the graph has a k-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 G as lcr(G).

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 k.


Since the Heawood graph and complete graph K_6 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 K_n (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.

See also

Graph Crossing Number, k-Planar Graph, Rectilinear Local Crossing Number

Explore with Wolfram|Alpha


Ábrego, B. M. and Fernández-Merchant, S. "The Rectilinear Local Crossing Number of K_n." J. Combin. Th. Ser. A 151, 131-145, Klerk, E.; Pasechnik, D. V.; and Schrijver, A. "Reduction of Symmetric Semidefinite Programs Using the Regular *-Representation." Math. Program. 109, 613-624, 2007.Guy, R. .K; Jenkyns, T.; and Schaer, J. "The Toroidal Crossing Number of the Complete Graph." J. Combin. Th. 4, 376-390, 1968.Kainen, P. C. "Thickness and Coarseness of Graphs." Abh. Math. Semin. Univ. Hamburg 39, 88-95, 1973.Ringel, G. "Ein Sechsfarbenproblem auf der Kugel." Abh. Math. Sem. Univ. Hamburg 29, 107-117, 1965.Schaefer, M. "The Graph Crossing Number and Its Variants: A Survey." Electron. J. Combin., DS21, pp. 43-45, May 15, 2013.Thomassen, C. "Rectilinear Drawings of Graphs." J. Graph Th. 12, 335-341, 1988.

Cite this as:

Weisstein, Eric W. "Local Crossing Number." From MathWorld--A Wolfram Web Resource.

Subject classifications