graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the crossing number of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

is the lowest number of edge crossings of a plane

drawing Drawing is a form of visual art in which an artist uses instruments to mark paper or other two-dimensional surface. Drawing instruments include graphite pencils, pen and ink, various kinds of paints, inked brushes, colored pencils, crayons, ...

of the graph . For instance, a graph is

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing. The study of crossing numbers originated in Turán's brick factory problem, in which

Pál Turán Pál Turán (; 18 August 1910 – 26 September 1976) also known as Paul Turán, was a Hungarian mathematician who worked primarily in extremal combinatorics. He had a long collaboration with fellow Hungarian mathematician Paul Erdős, lasting ...

asked for a factory plan that minimized the number of crossings between tracks connecting brick kilns to storage sites. Mathematically, this problem can be formalized as asking for the crossing number of a

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...

. The same problem arose independently in

sociology Sociology is a social science that focuses on society, human social behavior, patterns of Interpersonal ties, social relationships, social interaction, and aspects of culture associated with everyday life. It uses various methods of Empirical ...

at approximately the same time, in connection with the construction of

sociogram A sociogram is a graphic representation of social links that a person has. It is a graph drawing that plots the structure of interpersonal relations in a group situation. Overview Sociograms were developed by Jacob L. Moreno to analyze choice ...

s. Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous formula for the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

s. The

crossing number inequality In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the Crossing number (graph theory), minimum number of crossings of a given Graph (discrete mathematics), graph, as a function of the number ...

states that, for graphs where the number of edges is sufficiently larger than the number of vertices, the crossing number is at least proportional to . It has applications in

VLSI Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) c ...

design and

incidence geometry In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An ''incide ...

. Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, the rectilinear crossing number, requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a

is essentially the same as the minimum number of

convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...

quadrilaterals In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...

determined by a set of points in general position. The problem of determining this number is closely related to the

happy ending problem In mathematics, the "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein) is the following statement: This was one of the original results that led to the development of Ramsey t ...

Definitions

For the purposes of defining the crossing number, a drawing of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is a mapping from the vertices of the graph to disjoint points in the plane, and from the edges of the graph to curves connecting their two endpoints. No vertex should be mapped onto an edge that it is not an endpoint of, and whenever two edges have curves that intersect (other than at a shared endpoint) their intersections should form a finite set of proper crossings, where the two curves are

transverse Transverse may refer to: *Transverse engine, an engine in which the crankshaft is oriented side-to-side relative to the wheels of the vehicle *Transverse flute, a flute that is held horizontally * Transverse force (or ''Euler force''), the tangen ...

. A crossing is counted separately for each of these crossing points, for each pair of edges that cross. The crossing number of a graph is then the minimum, over all such drawings, of the number of crossings in a drawing. Some authors add more constraints to the definition of a drawing, for instance that each pair of edges have at most one intersection point (a shared endpoint or crossing). For the crossing number as defined above, these constraints make no difference, because a crossing-minimal drawing cannot have edges with multiple intersection points. If two edges with a shared endpoint cross, the drawing can be changed locally at the crossing point, leaving the rest of the drawing unchanged, to produce a different drawing with one fewer crossing. And similarly, if two edges cross two or more times, the drawing can be changed locally at two crossing points to make a different drawing with two fewer crossings. However, these constraints are relevant for variant definitions of the crossing number that, for instance, count only the numbers of pairs of edges that cross rather than the number of crossings.

Special cases

As of April 2015, crossing numbers are known for very few graph families. In particular, except for a few initial cases, the crossing number of complete graphs, bipartite complete graphs, and products of cycles all remain unknown, although there has been some progress on lower bounds.

Complete bipartite graphs

During

World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...

, Hungarian mathematician

was forced to work in a brick factory, pushing wagon loads of bricks from kilns to storage sites. The factory had tracks from each kiln to each storage site, and the wagons were harder to push at the points where tracks crossed each other, from which Turán was led to ask his brick factory problem: how can the kilns, storage sites, and tracks be arranged to minimize the total number of crossings? Mathematically, the kilns and storage sites can be formalized as the vertices of a

, with the tracks as its edges. A factory layout can be represented as a drawing of this graph, so the problem becomes: what is the minimum possible number of crossings in a drawing of a

Kazimierz Zarankiewicz Kazimierz Zarankiewicz (2 May 1902 – 5 September 1959) was a Polish mathematician and Professor at the Warsaw University of Technology who was interested primarily in topology and graph theory. Biography Zarankiewicz was born in Częstochowa ...

attempted to solve Turán's brick factory problem; his proof contained an error, but he established a valid

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...

of :

\textrm(K_) \le \left\lfloor\frac\right\rfloor\left\lfloor\frac\right\rfloor\left\lfloor\frac\right\rfloor\left\lfloor\frac\right\rfloor

for the crossing number of the complete bipartite graph . This bound has been conjectured to be the optimal number of crossings for all complete bipartite graphs.

Complete graphs and graph coloring

The problem of determining the crossing number of the

was first posed by Anthony Hill, and appeared in print in 1960. Hill and his collaborator

John Ernest John Ernest (May 6, 1922 – July 21, 1994) was an American-born constructivist abstract artist. He was born in Philadelphia, in 1922. After living and working in Sweden and Paris from 1946 to 1951, he moved to London, England, where he lived and w ...

were two constructionist artists fascinated by mathematics. They not only formulated this problem but also originated a conjectural formula for this crossing number, which Richard K. Guy published in 1960. Namely, it is known that there always exists a drawing with :

\textrm(K_p) \le \frac \left\lfloor\frac\right\rfloor\left\lfloor\frac\right\rfloor\left\lfloor\frac\right\rfloor\left\lfloor\frac\right\rfloor

crossings. This formula gives values of for ; see sequence in the

On-line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...

. The conjecture is that there can be no better drawing, so that this formula gives the optimal number of crossings for the complete graphs. An independent formulation of the same conjecture was made by Thomas L. Saaty in 1964. Saaty further verified that this formula gives the optimal number of crossings for and Pan and Richter showed that it also is optimal for . The Albertson conjecture, formulated by Michael O. Albertson in 2007, states that, among all graphs with

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

, the complete graph has the minimum number of crossings. That is, if the conjectured formula for the crossing number of the complete graph is correct, then every -chromatic graph has crossing number at least equal to the same formula. The Albertson conjecture is now known to hold for .

Cubic graphs

The smallest

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bi ...

s with crossing numbers 1–8 and 11 are known . The smallest 1-crossing cubic graph is the

, with 6 vertices. The smallest 2-crossing cubic graph is the

Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...

, with 10 vertices. The smallest 3-crossing cubic graph is the

Heawood graph Heawood is a surname. Notable people with the surname include: * Jonathan Heawood, British journalist *Percy John Heawood (1861–1955), British mathematician **Heawood conjecture ** Heawood graph **Heawood number In mathematics, the Heawood numbe ...

, with 14 vertices. The smallest 4-crossing cubic graph is the Möbius-Kantor graph, with 16 vertices. The smallest 5-crossing cubic graph is the

Pappus graph In the mathematical field of graph theory, the Pappus graph is a bipartite 3- regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek ...

, with 18 vertices. The smallest 6-crossing cubic graph is the

Desargues graph In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level ...

, with 20 vertices. None of the four 7-crossing cubic graphs, with 22 vertices, are well known. The smallest 8-crossing cubic graphs include the

Nauru graph In the mathematics, mathematical field of graph theory, the Nauru graph is a symmetric graph, symmetric bipartite graph, bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag o ...

and the

McGee graph In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges. The McGee graph is the unique (3,7)-cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage tha ...

or (3,7)-

cage graph In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an is defined to be a graph in which each vertex has exactly neighbors, and in which the shortest cycle has le ...

, with 24 vertices. The smallest 11-crossing cubic graphs include the

Coxeter graph In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter. Properties The Coxeter ...

with 28 vertices. In 2009, Pegg and Exoo conjectured that the smallest cubic graph with crossing number 13 is the

Tutte–Coxeter graph In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph ...

and the smallest cubic graph with crossing number 170 is the

Tutte 12-cage In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)- cage . It was discovered by C. T. Benson in 1966. ...

Complexity and approximation

In general, determining the crossing number of a graph is hard; Garey and

Johnson Johnson is a surname of Anglo-Norman origin meaning "Son of John". It is the second most common in the United States and 154th most common in the world. As a common family name in Scotland, Johnson is occasionally a variation of ''Johnston'', a ...

showed in 1983 that it is an NP-hard problem. In fact the problem remains NP-hard even when restricted to

s and to near-planar graphs (graphs that become planar after removal of a single edge). A closely related problem, determining the rectilinear crossing number, is

complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...

for the

existential theory of the reals In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form \exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n), where the variables X_i are interpre ...

. On the positive side, there are efficient algorithms for determining whether the crossing number is less than a fixed constant . In other words, the problem is

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

. It remains difficult for larger , such as . There are also efficient

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

s for approximating on graphs of bounded degree. In practice

heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...

algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. These algorithms are used in the Rectilinear Crossing Number

distributed computing A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...

project.

The crossing number inequality

For an undirected simple graph with vertices and edges such that the crossing number is always at least ::

\operatorname(G) \geq \frac.

This relation between edges, vertices, and the crossing number was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi, and by Leighton. It is known as the

or crossing lemma. The constant is the best known to date, and is due to Ackerman. The constant can be lowered to , but at the expense of replacing with the worse constant of . The motivation of Leighton in studying crossing numbers was for applications to

design in theoretical computer science. Later, Székely also realized that this inequality yielded very simple proofs of some important theorems in

, such as Beck's theorem and the Szemerédi-Trotter theorem, and

Tamal Dey Tamal Krishna Dey (born 1964) is an Indian mathematician and computer scientist specializing in computational geometry and computational topology. He is a professor at Purdue University. Education and career Dey graduated from Jadavpur Univers ...

used it to prove upper bounds on geometric ''k''-sets.

Variations

If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings. The rectilinear crossing number is defined to be the minimum number of crossings of a drawing of this type. It is always at least as large as the crossing number, and is larger for some graphs. The rectilinear crossing numbers for through are , () and values up to are known, with requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project. A graph has local crossing number if it can be drawn with at most crossings per edge, but not fewer. The graphs that can be drawn with at most crossings per edge are also called -planar. Other variants of the crossing number include the pairwise crossing number (the minimum number of pairs of edges that cross in any drawing) and the odd crossing number (the number of pairs of edges that cross an odd number of times in any drawing). The odd crossing number is at most equal to the pairwise crossing number, which is at most equal to the crossing number. However, by the

Hanani–Tutte theorem In topological graph theory, the Hanani–Tutte theorem is a result on the parity of edge crossings in a graph drawing. It states that every drawing in the plane of a non-planar graph contains a pair of independent edges (not both sharing an end ...

, whenever one of these numbers is zero, they all are. surveys many such variants.

References

{{Reflist, 30em, refs= {{cite web, title=On topological graphs with at most four crossings per edge, first=Eyal, last=Ackerman, url=http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf, year=2013, url-status=dead, archive-url=https://web.archive.org/web/20140714181310/http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf, archive-date=2014-07-14 {{cite conference, author1=Ajtai, M., author-link=Miklós Ajtai, author2=Chvátal, V., author2-link=Václav Chvátal, author3=Newborn, M. , author4=Szemerédi, E. , author4-link=Endre Szemerédi , title=Crossing-free subgraphs, conference=Theory and Practice of Combinatorics, series=North-Holland Mathematics Studies, volume=60, year=1982, pages=9–12, mr=0806962 {{cite book, title= Crossing Numbers of Graphs, title-link= Crossing Numbers of Graphs, first=Marcus, last=Schaefer, publisher=CRC Press, year=2018 {{cite arXiv , first1=János , last1=Barát , first2=Géza , last2=Tóth , year=2009 , title=Towards the Albertson Conjecture , eprint=0909.0413 , class=math.CO {{cite journal, title=The graphic presentation of sociometric data, first=Urie, last=Bronfenbrenner, author-link=Urie Bronfenbrenner, journal=Sociometry, volume=7, issue=3, year=1944, pages=283–289, doi=10.2307/2785096, jstor=2785096, quote=The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines. {{cite journal , author=Cabello S. and Mohar B. , title=Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard , year=2013 , journal=

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ...

, volume=42 , issue=5 , pages=1803–1829 , doi=10.1137/120872310 , arxiv=1203.5944 , s2cid=6535755 {{cite journal , author = Dey, T. K. , author-link = Tamal Dey , title = Improved bounds for planar ''k''-sets and related problems , journal =

Discrete and Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geome ...

, volume = 19 , issue = 3 , year = 1998 , pages = 373–382 , doi = 10.1007/PL00009354 , mr = 1608878 , doi-access = free {{Cite journal , first1=Guy , last1=Even , first2=Sudipto , last2=Guha , first3 = Baruch , last3 = Schieber , author3-link = Baruch Schieber , title=Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas , journal=

, volume=32 , year=2003 , pages=231–252 , doi=10.1137/S0097539700373520 , issue=1 {{cite web , last=Exoo , first=G. , url=http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/ , title=Rectilinear Drawings of Famous Graphs {{cite journal , author1=Garey, M. R. , author-link=Michael Garey , author2=Johnson, D. S. , author2-link=David S. Johnson , title=Crossing number is NP-complete , journal=SIAM Journal on Algebraic and Discrete Methods , volume=4 , pages=312–316 , year=1983 , mr=0711340 , doi=10.1137/0604033 , issue=3 {{Cite journal , last=Grohe , first=M., author-link=Martin Grohe , title=Computing crossing numbers in quadratic time , journal= Journal of Computer and System Sciences, volume=68 , issue=2 , year=2005 , pages=285–302 , mr=2059096 , doi=10.1016/j.jcss.2003.07.008 , arxiv=cs/0009010 {{Cite journal , title=A combinatorial problem , first1=R. K. , last1=Guy , author-link=Richard K. Guy , journal=Nabla (Bulletin of the Malayan Mathematical Society) , volume=7 , year=1960 , pages=68–72 {{cite book , last = Guy , first = Richard K. , author-link = Richard K. Guy , contribution = The decline and fall of Zarankiewicz's theorem , mr = 0253931 , pages = 63–69 , publisher = Academic Press, New York , title = Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , year = 1969. {{cite journal , author=Hliněný, P. , title=Crossing number is hard for cubic graphs , year=2006 , journal=

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, series=Series B , volume=96 , issue=4 , pages=455–471 , mr=2232384 , doi=10.1016/j.jctb.2005.09.009 , doi-access=free {{citation, first1=Michael, last1=Haythorpe, first2=Alex, last2=Newcombe, title=There are no Cubic Graphs on 26 Vertices with Crossing Number 11, year=2018, arxiv=1804.10336 {{Cite conference , first1= Ken-ichi , last1=Kawarabayashi , author1-link = Ken-ichi Kawarabayashi , first2=Bruce , last2=Reed , author2-link = Bruce Reed (mathematician) , title=Computing crossing number in linear time , conference= Proceedings of the 29th Annual ACM Symposium on Theory of Computing , year=2007 , pages=382–390 , doi=10.1145/1250790.1250848 , isbn= 978-1-59593-631-8 {{Cite journal , last1=de Klerk , first1=E. , last2=Maharry , first2=J. , last3=Pasechnik , first3=D. V. , last4=Richter , first4=B. , last5=Salazar , first5=G. , year=2006 , url=https://research.tilburguniversity.edu/en/publications/improved-bounds-for-the-crossing-numbers-of-kmn-and-kn , title=Improved bounds for the crossing numbers of ''K_m,n'' and ''K_n'' , journal=

SIAM Journal on Discrete Mathematics '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was estab ...

, volume=20 , issue=1 , pages=189–202 , doi=10.1137/S0895480104442741 , arxiv=math/0404142 , s2cid=1509054 {{cite book , author=Leighton, T. , author-link=F. Thomson Leighton , title=Complexity Issues in VLSI , series=Foundations of Computing Series , publisher=MIT Press , location=Cambridge, MA , year=1983 {{MathWorld, urlname=GraphCrossingNumber, title=Graph Crossing Number {{cite book , last1 = Pach , first1 = János , author1-link = János Pach , last2 = Sharir , first2 = Micha , author2-link = Micha Sharir , contribution = 5.1 Crossings—the Brick Factory Problem , pages = 126–127 , publisher =

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

, series = Mathematical Surveys and Monographs , title = Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures , volume = 152, year = 2009 {{cite conference , last1 = Pach , first1 = J. , author1-link = János Pach , last2 = Tóth , first2 = G. , contribution = Which crossing number is it, anyway? , doi = 10.1109/SFCS.1998.743512 , pages = 617–626 , title = Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998) , year = 1998. {{cite journal , last1 = Pan , first1 = Shengjun , last2 = Richter , first2 = R. Bruce , doi = 10.1002/jgt.20249 , issue = 2 , journal =

Journal of Graph Theory The ''Journal of Graph Theory'' is a peer-reviewed mathematics journal specializing in graph theory and related areas, such as structural results about graphs, graph algorithms with theoretical emphasis, and discrete optimization on graphs. The ...

, mr = 2350621 , pages = 128–134 , title = The crossing number of {{math, ''K''₁₁ is {{math, 100 , volume = 56 , year = 2007, s2cid = 37155969 . {{Cite journal , last1=Pegg , first1=E. T. , author1-link=Ed Pegg, Jr., last2=Exoo , first2=G. , title=Crossing Number Graphs , journal=Mathematica Journal , volume=11 , year=2009 , issue=2 , doi=10.3888/tmj.11.2-2 {{cite conference , last1 = Purchase , first1 = Helen C. , last2 = Cohen , first2 = Robert F. , last3 = James , first3 = Murray I. , editor-last = Brandenburg , editor-first = Franz-Josef , contribution = Validating graph drawing aesthetics , doi = 10.1007/BFb0021827 , pages = 435–446 , publisher = Springer , series = Lecture Notes in Computer Science , title = Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings , volume = 1027 , year = 1995, doi-access = free . {{cite web , url=http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ , archive-url=https://archive.today/20121230191705/http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ , url-status=dead , archive-date=2012-12-30 , title=Rectilinear Crossing Number project , author=Oswin Aichholzer , an
Rectilinear Crossing Number
on the Institute for Software Technology at Graz, University of Technology (2009). {{cite journal , last = Ringel , first = Gerhard , author-link = Gerhard Ringel , doi = 10.1007/BF02996313 , journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , language = German , mr = 0187232 , pages = 107–117 , title = Ein Sechsfarbenproblem auf der Kugel , volume = 29 , year = 1965, issue = 1–2 , s2cid = 123286264 {{Cite journal , title=The minimum number of intersections in complete graphs , first1=T.L. , last1=Saaty , author-link=Thomas L. Saaty , journal=

Proceedings of the National Academy of Sciences of the United States of America ''Proceedings of the National Academy of Sciences of the United States of America'' (often abbreviated ''PNAS'' or ''PNAS USA'') is a peer-reviewed multidisciplinary scientific journal. It is the official journal of the National Academy of Sc ...

, volume=52 , year=1964 , issue=3 , pages=688–690 , doi=10.1073/pnas.52.3.688, bibcode=1964PNAS...52..688S , pmc=300329 , pmid=16591215, doi-access=free {{Cite conference, first=Marcus, last=Schaefer, title=Complexity of some geometric and topological problems, url=http://ovid.cs.depaul.edu/documents/convex.pdf, conference= Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, series=Lecture Notes in Computer Science, publisher=Springer-Verlag, volume=5849, pages=334–344, doi=10.1007/978-3-642-11805-0_32 , year=2010, isbn=978-3-642-11804-3, doi-access=free. {{cite journal , last1 = Schaefer , first1 = Marcus , journal =

The Electronic Journal of Combinatorics The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin ( G ...

, at = DS21 , title = The graph crossing number and its variants: a survey , year = 2014 , url = https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21 {{Cite journal , title=The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability , first1=Edward R. , last1=Scheinerman, author1-link=Ed Scheinerman , first2=Herbert S. , last2=Wilf, author2-link=Herbert Wilf , journal= American Mathematical Monthly , volume=101 , issue=10 , year=1994 , pages=939–943 , doi=10.2307/2975158 , jstor=2975158 {{cite journal , author=Székely, L. A. , title=Crossing numbers and hard Erdős problems in discrete geometry , journal=

Combinatorics, Probability and Computing ''Combinatorics, Probability and Computing'' is a peer-reviewed scientific journal in mathematics published by Cambridge University Press. Its editor-in-chief is Béla Bollobás ( DPMMS and University of Memphis). History The journal was estab ...

, volume=6 , year=1997 , pages=353–358 , mr=1464571 , doi=10.1017/S0963548397002976 , issue=3 , s2cid=36602807 {{cite journal , doi=10.1002/jgt.3190010105 , last=Turán , first=P., author-link=Pál Turán , title=A Note of Welcome , journal=

, volume=1 , pages=7–9 , year=1977 {{cite journal , last=Zarankiewicz , first=K. , author-link=Kazimierz Zarankiewicz, title=On a Problem of P. Turán Concerning Graphs , journal=

Fundamenta Mathematicae ''Fundamenta Mathematicae'' is a peer-reviewed scientific journal of mathematics with a special focus on the foundations of mathematics, concentrating on set theory, mathematical logic, topology and its interactions with algebra, and dynamical sys ...

, volume=41 , pages=137–145 , year=1954 , doi=10.4064/fm-41-1-137-145 , doi-access=free Topological graph theory Graph invariants Graph drawing Geometric intersection