# Crossing numbers

## The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture Keywords: complete graph; crossing number

## The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture Keywords: complete bipartite graph; crossing number

## The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number of is the minimum number of crossings in all drawings of in the plane.

The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.

Conjecture Keywords: crossing number; hypercube

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let be a sequence of nonnegative integers which strictly decreases until .

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus with crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

## Crossing numbers and coloring ★★★

Author(s): Albertson

We let denote the crossing number of a graph .

Conjecture   Every graph with satisfies .

Keywords: coloring; complete graph; crossing number

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

Author(s): Pach; Tóth

Problem   Does the following equality hold for every graph ? The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number
{"ft_lang_label":"__label__en","ft_lang_prob":0.8575578,"math_prob":0.9439661,"size":1759,"snap":"2020-34-2020-40","text_gpt3_token_len":413,"char_repetition_ratio":0.24330485,"word_repetition_ratio":0.19485295,"special_character_ratio":0.2239909,"punctuation_ratio":0.14150943,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99443024,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80],"im_url_duplicate_count":[null,null,null,null,null,null,null,10,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,7,null,null,null,null,null,8,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-03T17:51:39Z\",\"WARC-Record-ID\":\"<urn:uuid:4df62fb8-17fc-4b01-9eda-3d57a1d93e05>\",\"Content-Length\":\"23491\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:1d9cf8e0-706a-4460-b500-0b3d5e1f5227>\",\"WARC-Concurrent-To\":\"<urn:uuid:66dc0736-8b14-4b40-8034-91ef71cab525>\",\"WARC-IP-Address\":\"31.31.74.53\",\"WARC-Target-URI\":\"http://openproblemgarden.org/category/crossing_numbers\",\"WARC-Payload-Digest\":\"sha1:BTAJ5VYZT2JHYEQ633OCEZAXCIIVDQM2\",\"WARC-Block-Digest\":\"sha1:DHOHUUTNSDSRKZ27FQ3D67UER5VTNR44\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439735823.29_warc_CC-MAIN-20200803170210-20200803200210-00542.warc.gz\"}"}