Topological graph

<h2 id="extremal-problems-for-topological-graphs">Extremal problems for topological graphs</h2>
A fundamental problem in <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal graph theory</a> is the following: what is the maximum number of edges that a graph of n vertices can have if it contains no subgraph belonging to a given class of forbidden subgraphs? The prototype of such results is <a href="/facts/Tur%C3%A1n%27s_theorem/opMCT84y">Turán's theorem</a>, where there is one forbidden subgraph: a complete graph with k vertices (k is fixed). Analogous questions can be raised for topological and geometric graphs, with the difference
that now certain geometric subconfigurations are forbidden.
Historically, the first instance of such a theorem is due to <a href="/facts/Paul_Erd%C5%91s/63LoUTe1">Paul Erdős</a>, who extended
a result of <a href="/facts/Heinz_Hopf/PMks10NV">Heinz Hopf</a> and <a href="/facts/Erika_Pannwitz/PPJRgAg9">Erika Pannwitz</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> He proved that the maximum number of edges that a geometric graph with n > 2 vertices can have without containing two disjoint edges (that cannot even share an endpoint) is n. <a href="/facts/John_Horton_Conway/g3PA1zoK">John Conway</a> conjectured that this statement can be generalized to simple topological graphs. A topological graph is called "simple" if any pair of its edges share at most one point, which is either an endpoint or a common interior point at which the two edges properly cross. Conway's <a href="/facts/Thrackle/KAGs310p">thrackle</a> conjecture can now be reformulated as follows: A simple topological graph with n > 2 vertices and no two disjoint edges has at most n edges.
The first linear upper bound on the number of edges of such a graph was established by <a href="/facts/L%C3%A1szl%C3%B3_Lov%C3%A1sz/X0VB38Ee">Lovász</a> et al.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
The best known upper bound, 1.3984n, was proved by Fulek and <a href="/facts/J%C3%A1nos_Pach/x1t8LFL7">Pach</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> Apart from geometric graphs, Conway's thrackle conjecture is known to be true for x-monotone topological graphs.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> A topological graph is said to be x-monotone if every vertical line intersects every edge in at most one point.
<a href="/facts/Noga_Alon/tuqq2GUl">Alon</a> and <a href="/facts/Paul_Erd%C5%91s/63LoUTe1">Erdős</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> initiated the investigation of the generalization of the above question to the case where the forbidden configuration consists of k disjoint edges (k > 2). They proved that the number of edges of a geometric graph of n
vertices, containing no 3 disjoint edges is O(n). The optimal bound of roughly 2.5n was determined by Černý.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
For larger values of k, the first linear upper bound, 
 
 
 
 O
 (
 
 k
 
 4
 
 
 n
 )
 
 
 {\displaystyle O(k^{4}n)}
 
, was established by Pach and Töröcsik.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> This was improved by Tóth to 
 
 
 
 O
 (
 
 k
 
 2
 
 
 n
 )
 
 
 {\displaystyle O(k^{2}n)}
 
.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
For the number of edges in a simple topological graph with no k disjoint edges, only an 
 
 
 
 O
 (
 n
 
 log
 
 4
 k
 −
 8
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log ^{4k-8}n)}
 
 upper bound is known.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> This implies that every complete simple topological graph with n vertices has at least 
 
 
 
 c
 
 
 
 log
 ⁡
 n
 
 
 log
 ⁡
 log
 ⁡
 n
 
 
 
 
 
 {\displaystyle c{\frac {\log n}{\log \log n}}}
 
 pairwise disjoint edges, which was improved to 
 
 
 
 c
 
 n
 
 
 
 1
 2
 
 
 −
 ϵ
 
 
 
 
 {\displaystyle cn^{{\frac {1}{2}}-\epsilon }}
 
 by Ruiz-Vargas.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> It is possible that this lower bound can be further improved to cn, where c > 0 is a constant.

<h3>Quasi-planar graphs</h3>
A common interior point of two edges, at which the first edge passes from one side of the second edge to the other, is called a crossing. Two edges of a topological graph cross each other if they determine a crossing. For any integer k > 1, a topological or geometric graph is called k-quasi-planar if it has no k pairwise crossing edges.
Using this terminology, if a topological graph is 2-quasi-planar, then it is a planar graph.
It follows from <a href="/facts/Euler%27s_polyhedral_formula/JCjzWUr2">Euler's polyhedral formula</a> that every planar graph with n > 2 vertices has at most 3n − 6 edges. Therefore, every 2-quasi-planar graph with n > 2 vertices has at most 3n − 6 edges.
It has been conjectured by Pach et al.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> that every k-quasi-planar topological graph with n vertices has at most c(k)n
edges, where c(k) is a constant depending only on k. This conjecture is known to be true for k = 3
<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> and k = 4.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> It is also known to be true for convex geometric graphs (that is for geometric graphs
whose vertices form the vertex set of a convex n-gon),<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> and for k-quasi-planar topological graphs whose edges are drawn as x-monotone curves, all of which cross a vertical line.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a><a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
The last result implies that every k-quasi-planar topological graph with n vertices, whose edges are drawn as x-monotone curves has at most c(k)n log n edges for a suitable constant c(k). For geometric graphs, this was proved earlier by Valtr.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> The best known general <a href="/facts/Upper_bound/YJje9oC2">upper bound</a> for the number of edges of a k-quasi-planar topological graph is 
 
 
 
 n
 
 log
 
 O
 (
 log
 ⁡
 k
 )
 
 
 ⁡
 n
 
 
 {\displaystyle n\log ^{O(\log k)}n}
 
.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>
This implies that every complete topological graph with n vertices has at least 
 
 
 
 
 n
 
 
 1
 
 O
 (
 log
 ⁡
 log
 ⁡
 n
 )
 
 
 
 
 
 
 {\displaystyle n^{\frac {1}{O(\log \log n)}}}
 
pairwise crossing edges, which was improved to a quasi linear bound in the case of geometric graph.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<h2 id="crossing-numbers">Crossing numbers</h2>
Main article: <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">Crossing number (graph theory)</a>
Ever since <a href="/facts/P%C3%A1l_Tur%C3%A1n/nkWkQB6M">Pál Turán</a> coined <a href="/facts/Tur%C3%A1n%27s_brick_factory_problem/o2770HsJ">his brick factory problem</a>
<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> during <a href="/facts/World_War_II/2efV5L1U">World War II</a>, the determination or estimation of <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">crossing numbers of graphs</a> has been a popular theme in graph theory and in the theory of algorithms<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> that is abundant with famous long standing open problems such as the <a href="/facts/Albertson_conjecture/gN8afN37">Albertson conjecture</a>, <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">Harary-Hill's conjecture</a><a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> or the still unsolved <a href="/facts/Tur%C3%A1n%27s_brick_factory_problem/o2770HsJ">Turán's brick factory problem</a>.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> However, the publications in the subject (explicitly or implicitly) used several competing definitions of crossing numbers. This was pointed out by Pach and Tóth,<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> who introduced the following terminology.
<a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">Crossing number</a> (of a graph G): The minimum number of crossing points over all drawings of G in the plane (that is, all of its representations as a topological graph) with the property that no three edges pass through the same point. It is denoted by cr(G).
Pair-crossing number: The minimum number of crossing pairs of edges over all drawings of G. It is denoted by pair-cr(G).
Odd-crossing number: The minimum number of those pairs of edges that cross an odd number of times, over all drawings of G. It is denoted by odd-cr(G).
These parameters are not unrelated. One has odd-cr(G) ≤ pair-cr(G) ≤ cr(G) for every graph G. It is known that cr(G) ≤ 2(odd-cr(G))2<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a> and 
 
 
 
 O
 (
 pcr
 ⁡
 (
 G
 
 )
 
 
 3
 2
 
 
 
 
 log
 
 2
 
 
 ⁡
 pcr
 ⁡
 (
 G
 )
 )
 
 
 {\displaystyle O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))}
 
<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a>
and that there exist infinitely many graphs for which pair-cr(G) ≠ odd-cr(G).<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a>
<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a> No examples are known for which the crossing number and the pair-crossing number are not the same. It follows from the <a href="/facts/Hanani%E2%80%93Tutte_theorem/IU8MfuMR">Hanani–Tutte theorem</a><a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>
<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> that odd-cr(G) = 0 implies cr(G) = 0.
It is also known that odd-cr(G) = k implies cr(G)=k for k = 1, 2, 3.<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a>
Another well researched graph parameter is the following.
Rectilinear crossing number: The minimum number of crossing points over all straight-line drawings of G in the plane (that is, all of its representations as a geometric graph) with the property that no three edges pass through the same point. It is denoted by lin-cr(G).
By definition, one has cr(G) ≤ lin-cr(G) for every graph G. It was shown by Bienstock and Dean that there are graphs with crossing number 4 and with arbitrarily large rectilinear crossing number.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a>
Computing the crossing number is <a href="/facts/NP-completeness/NFPv56DU">NP-complete</a><a class="footnote-ref" id="fnref:35" href="#fn:35">35</a> in general. Therefore a large body of research focuses on its estimates. The <a href="/facts/Crossing_number_inequality/XaqTQlFT">Crossing Lemma</a> is a cornerstone result that provides widely applicable lower bounds on the crossing number. Several interesting variants and generalizations of the Crossing Lemma are known for Jordan curves<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a>
<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a> and degenerate crossing number,<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a>[38] where the latter relates the notion of the crossing number to the <a href="/facts/Graph_embedding/IyBA3ttM">graph genus</a>.

<h2 id="ramsey-type-problems-for-geometric-graphs">Ramsey-type problems for geometric graphs</h2>
In traditional <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a typical <a href="/facts/Ramsey_theory/CzLLM2j8">Ramsey-type result</a> states that if we color the edges of a sufficiently large complete graph with a fixed number of colors, then we necessarily find a monochromatic subgraph of a certain type.<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a> One can raise similar questions for geometric (or topological) graphs, except that now we look for monochromatic (one-colored) substructures satisfying certain geometric conditions.<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a>
One of the first results of this kind states that every complete geometric graph whose edges are colored with two colors contains a non-crossing monochromatic <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a>.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a> It is also true that every such geometric graph contains 
 
 
 
 
 ⌈
 
 
 
 n
 +
 1
 
 3
 
 
 ⌉
 
 
 
 {\displaystyle \left\lceil {\frac {n+1}{3}}\right\rceil }
 
 disjoint edges of the same color.<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a> The existence of a non-crossing monochromatic path of size at least cn, where c > 0 is a constant, is a long-standing open problem. It is only known that every complete geometric graph on n vertices contains a non-crossing monochromatic path of length at least 
 
 
 
 
 n
 
 
 2
 3
 
 
 
 
 
 {\displaystyle n^{\frac {2}{3}}}
 
.<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a>

<h2 id="topological-hypergraphs">Topological hypergraphs</h2>
If we view a topological graph as a topological realization of a 1-dimensional <a href="/facts/Simplicial_complex/fF2282CF">simplicial complex</a>, it is natural to ask how the above extremal and Ramsey-type problems generalize to topological realizations of d-dimensional simplicial complexes. 
There are some initial results in this direction, but it requires further research to identify the key notions and problems.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a><a class="footnote-ref" id="fnref:45" href="#fn:45">45</a><a class="footnote-ref" id="fnref:46" href="#fn:46">46</a>
Two vertex disjoint simplices are said to cross if their relative interiors have a point in common. A set of k > 3 simplices strongly cross if no 2 of them share a vertex, but their relative interiors have a point common.
It is known that a set of d-dimensional simplices spanned by n points in 
 
 
 
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \mathbb {R} ^{d}}
 
 without a pair of crossing simplices can have at most 
 
 
 
 O
 (
 
 n
 
 d
 
 
 )
 
 
 {\displaystyle O(n^{d})}
 
 simplices and this bound is asymptotically tight.<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a> This result was generalized to sets of 2-dimensional simplices in 
 
 
 
 
 
 R
 
 
 2
 
 
 
 
 {\displaystyle \mathbb {R} ^{2}}
 
 without three strongly crossing simplices.[47]
If we forbid k strongly crossing simplices, the corresponding best known upper bound is 
 
 
 
 O
 (
 
 n
 
 d
 +
 1
 −
 δ
 
 
 )
 
 
 {\displaystyle O(n^{d+1-\delta })}
 
,<a class="footnote-ref" id="fnref:48" href="#fn:48">48</a> for some 
 
 
 
 δ
 =
 δ
 (
 k
 ,
 d
 )
 <
 1
 
 
 {\displaystyle \delta =\delta (k,d)<1}
 
. This result follows from the colored <a href="/facts/Tverberg_theorem/SBqymV0T">Tverberg theorem</a>.<a class="footnote-ref" id="fnref:49" href="#fn:49">49</a> It is far from the conjectured bound of 
 
 
 
 O
 (
 
 n
 
 d
 
 
 )
 
 
 {\displaystyle O(n^{d})}
 
.<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a>
For any fixed k > 1, we can select at most 
 
 
 
 O
 (
 
 n
 
 ⌈
 
 
 d
 2
 
 
 ⌉
 
 
 )
 
 
 {\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}
 
 d-dimensional simplices spanned by a set of n points in 
 
 
 
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \mathbb {R} ^{d}}
 
 with the property that no k of them share a common interior point.<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a><a class="footnote-ref" id="fnref:52" href="#fn:52">52</a> This is asymptotically tight.
Two triangles in 
 
 
 
 
 
 R
 
 
 3
 
 
 
 
 {\displaystyle \mathbb {R} ^{3}}
 
 are said to be almost disjoint if they are disjoint or if they share only one vertex. It is an old problem of <a href="/facts/Gil_Kalai/oVnhYW0I">Gil Kalai</a> and others to decide whether the largest number of almost disjoint triangles that can be chosen on some vertex set of n points in 
 
 
 
 
 
 R
 
 
 3
 
 
 
 
 {\displaystyle \mathbb {R} ^{3}}
 
 is 
 
 
 
 o
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle o(n^{2})}
 
. It is known that there exists sets of n points for which this number is at least 
 
 
 
 c
 
 n
 
 
 3
 2
 
 
 
 
 
 {\displaystyle cn^{\frac {3}{2}}}
 
 for a suitable constant c > 0.<a class="footnote-ref" id="fnref:53" href="#fn:53">53</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hopf, Heinz; Pannwitz, Erika (1934), "Aufgabe nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114 <a href="/wiki/Heinz_Hopf" target="_blank">/wiki/Heinz_Hopf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Lovász, László; Pach, János; Szegedy, Mario (1997), "On Conway's thrackle conjecture", Discrete and Computational Geometry, 18 (4), Springer: 369–376, doi:10.1007/PL00009322 <a href="/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz" target="_blank">/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Fulek, Radoslav; Pach, János (2019), "Thrackles: An improved upper bound", Discrete Applied Mathematics, 259: 226–231, arXiv:1708.08037, doi:10.1016/j.dam.2018.12.025. <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Pach, János; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly, 118 (6): 544–548, doi:10.4169/amer.math.monthly.118.06.544, MR 2812285, S2CID 17558559 <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Alon, Noga; Erdős, Paul (1989), "Disjoint edges in geometric graphs", Discrete and Computational Geometry, 4 (4): 287–290, doi:10.1007/bf02187731 <a href="/wiki/Noga_Alon" target="_blank">/wiki/Noga_Alon</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Černý, Jakub (2005), "Geometric graphs with no three disjoint edges", Discrete and Computational Geometry, 34 (4): 679–695, doi:10.1007/s00454-005-1191-1 <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Pach, János; Töröcsik, Jenö (1994), "Some geometric applications of Dilworth's theorem", Discrete and Computational Geometry, 12: 1–7, doi:10.1007/BF02574361 <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Tóth, Géza (2000), "Note on geometric graphs", Journal of Combinatorial Theory, Series A, 89 (1): 126–132, doi:10.1006/jcta.1999.3001 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Pach, János; Tóth, Géza (2003), "Disjoint edges in topological graphs", Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers (PDF), Lecture Notes in Computer Science, vol. 3330, Springer-Verlag, pp. 133–140, doi:10.1007/978-3-540-30540-8_15 <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Ruiz-Vargas, Andres J. (2015), "Many disjoint edges in topological graphs", in Campêlo, Manoel; Corrêa, Ricardo; Linhares-Sales, Cláudia; Sampaio, Rudini (eds.), LAGOS'15 – VIII Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics, vol. 50, Elsevier, pp. 29–34, arXiv:1412.3833, doi:10.1016/j.endm.2015.07.006, S2CID 14865350 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Ruiz-Vargas, Andres J. (2017), "Many disjoint edges in topological graphs", Comput. Geom., 62: 1–13, arXiv:1412.3833, doi:10.1016/j.comgeo.2016.11.003 <a href="/wiki/Comput._Geom." target="_blank">/wiki/Comput._Geom.</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Pach, János; Shahrokhi, Farhad; Szegedy, Mario (1996), "Applications of the crossing number", Algorithmica, 16 (1), Springer: 111–117, doi:10.1007/BF02086610, S2CID 20375896 <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Agarwal K., Pankaj; Aronov, Boris; Pach, János; Pollack, Richard; Sharir, Micha (1997), "Quasi-planar graphs have a linear number of edges", Combinatorica, 17: 1–9, doi:10.1007/bf01196127, S2CID 8092013 <a href="/wiki/Pankaj_K._Agarwal" target="_blank">/wiki/Pankaj_K._Agarwal</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Ackerman, Eyal; Tardos, Gábor (2007), "On the maximum number of edges in quasi-planar graphs", Journal of Combinatorial Theory, Series A, 114 (3): 563–571, doi:10.1016/j.jcta.2006.08.002 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Ackerman, Eyal (2009), "On the maximum number of edges in topological graphs with no four pairwise crossing edges", Discrete and Computational Geometry, 41 (3): 365–375, doi:10.1007/s00454-009-9143-9 <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Capoyleas, Vasilis; Pach, János (1992), "A Turán-type theorem on chords of a convex polygon", Journal of Combinatorial Theory, Series B, 56 (1): 9–15, doi:10.1016/0095-8956(92)90003-G <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Suk, Andrew (2011), "k-quasi-planar graphs", Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7034, Springer-Verlag, pp. 266–277, arXiv:1106.0958, doi:10.1007/978-3-642-25878-7_26, S2CID 18681576 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Fox, Jacob; Pach, János; Suk, Andrew (2013), "The number of edges in k-quasi-planar graphs", SIAM Journal on Discrete Mathematics, 27 (1): 550–561, arXiv:1112.2361, doi:10.1137/110858586, S2CID 52317. <a href="/wiki/Jacob_Fox" target="_blank">/wiki/Jacob_Fox</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Valtr, Pavel (1997), "Graph drawing with no k pairwise crossing edges", Graph Drawing: 5th International Symposium, GD '97 Rome, Italy, September 18–20, 1997, Proceedings, Lecture Notes in Computer Science, vol. 1353, Springer-Verlag, pp. 205–218 <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Fox, Jacob; Pach, János (2012), "Coloring 
 
 
 
 
 K
 
 
 k
 
 
 
 
 
 {\displaystyle K_{\mbox{k}}}
 
-free intersection graphs of geometric objects in the plane" (PDF), European Journal of Combinatorics, 33 (5): 853–866, doi:10.1016/j.ejc.2011.09.021 A preliminary version of these results was announced in Proc. of Symposium on Computational Geometry (PDF), 2008, pp. 346–354, doi:10.1145/1377676.1377735, S2CID 15138458 <a href="http://real.mtak.hu/103565/1/coloring030208.pdf" target="_blank">http://real.mtak.hu/103565/1/coloring030208.pdf</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Pach, János; Rubin, Natan; Tardos, Gábor (2021), "Planar point sets determine many pairwise crossing segments", Advances in Mathematics, 386: 107779, arXiv:1904.08845, doi:10.1016/j.aim.2021.107779. <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Turán, Paul (1977), "A note of welcome", Journal of Graph Theory, 1: 7–9, doi:10.1002/jgt.3190010105 <a href="/wiki/Journal_of_Graph_Theory" target="_blank">/wiki/Journal_of_Graph_Theory</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Garey, M. R.; Johnson, D. S. (1983), "Crossing number is NP-complete", SIAM Journal on Algebraic and Discrete Methods, 4 (3): 312–316, doi:10.1137/0604033, MR 0711340{{citation}}: CS1 maint: multiple names: authors list (link) <a href="/wiki/Michael_Garey" target="_blank">/wiki/Michael_Garey</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Balogh, József; Lidický, Bernard; Salazar, Gelasio (2019), "Closing in on Hill's conjecture", SIAM Journal on Discrete Mathematics, 33 (3): 1261–1276, arXiv:1711.08958, doi:10.1137/17M1158859, S2CID 119672893 <a href="/wiki/SIAM_Journal_on_Discrete_Mathematics" target="_blank">/wiki/SIAM_Journal_on_Discrete_Mathematics</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Schaefer, Marcus (2012), "The graph crossing number and its variants: A survey", Electronic Journal of Combinatorics, 1000: DS21–May, doi:10.37236/2713 <a href="/wiki/Electronic_Journal_of_Combinatorics" target="_blank">/wiki/Electronic_Journal_of_Combinatorics</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Pach, János; Tóth, Géza (2000), "Which crossing number is it anyway?", Journal of Combinatorial Theory, Series B, 80 (2): 225–246, doi:10.1006/jctb.2000.1978 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Pach, János; Tóth, Géza (2000), "Which crossing number is it anyway?", Journal of Combinatorial Theory, Series B, 80 (2): 225–246, doi:10.1006/jctb.2000.1978 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Matoušek, Jiří (2014), "Near-optimal separators in string graphs", Combin. Probab. Comput., vol. 23, pp. 135–139, arXiv:1302.6482, doi:10.1017/S0963548313000400, S2CID 2351522 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Pelsmajer, Michael J.; Schaefer, Marcus; Štefankovič, Daniel (2008), "Odd crossing number and crossing number are not the same", Discrete and Computational Geometry, 39 (1–3): 442–454, doi:10.1007/s00454-008-9058-x A preliminary version of these results was reviewed in Proc. of 13th International Symposium on Graph Drawing, 2005, pp. 386–396, doi:10.1007/11618058_35 <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Tóth, Géza (2008), "Note on the pair-crossing number and the odd-crossing number", Discrete and Computational Geometry, 39 (4): 791–799, doi:10.1007/s00454-007-9024-z. <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Chojnacki (Hanani), Chaim (Haim) (1934), "Uber wesentlich unplattbar Kurven im dreidimensionale Raume", Fundamenta Mathematicae, 23: 135–142, doi:10.4064/fm-23-1-135-142 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Tutte, William T. (1970), "Toward a theory of crossing numbers", Journal of Combinatorial Theory, 8: 45–53, doi:10.1016/s0021-9800(70)80007-2 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Pelsmajer, Michael J.; Schaefer, Marcus; Štefankovič, Daniel (2007), "Removing even crossings", Journal of Combinatorial Theory, Series B, 97 (4): 489–500, doi:10.1016/j.jctb.2006.08.001 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Bienstock, Daniel; Dean, Nathaniel (1993), "Bounds for rectilinear crossing numbers", Journal of Graph Theory, 17 (3): 333–348, doi:10.1002/jgt.3190170308 <a href="/wiki/Journal_of_Graph_Theory" target="_blank">/wiki/Journal_of_Graph_Theory</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Garey, M. R.; Johnson, D. S. (1983). "Crossing number is NP-complete". SIAM Journal on Algebraic and Discrete Methods. 4 (3): 312–316. doi:10.1137/0604033. MR 0711340. <a href="/wiki/Michael_Garey" target="_blank">/wiki/Michael_Garey</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Pach, János; Rubin, Natan; Tardos, Gábor (2018), "A crossing lemma for Jordan curves", Advances in Mathematics, 331: 908–940, arXiv:1708.02077, doi:10.1016/j.aim.2018.03.015, S2CID 22278629 <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Pach, János; Tóth, Géza (2019), "Many touchings force many crossings", Journal of Combinatorial Theory, Series B, 137: 104–111, arXiv:1706.06829, doi:10.1016/j.jctb.2018.12.002 <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Ackerman, Eyal; Pinchasi, Rom (2013), "On the Degenerate Crossing Number", Discrete & Computational Geometry, 49 (3): 695–702, doi:10.1007/s00454-013-9493-1, S2CID 254030772 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1990), Ramsey Theory, Wiley <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Károlyi, Gyula (2013), "Ramsey-type problems for geometric graphs", in Pach, J. (ed.), Thirty essays on geometric graph theory, Springer <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Károlyi, Gyula J.; Pach, János; Tóth, Géza (1997), "Ramsey-type results for geometric graphs, I", Discrete and Computational Geometry, 18 (3): 247–255, doi:10.1007/PL00009317 <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Károlyi, Gyula J.; Pach, János; Tóth, Géza (1997), "Ramsey-type results for geometric graphs, I", Discrete and Computational Geometry, 18 (3): 247–255, doi:10.1007/PL00009317 <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Károlyi, Gyula J.; Pach, János; Tóth, Géza; Valtr, Pavel (1998), "Ramsey-type results for geometric graphs, II", Discrete and Computational Geometry, 20 (3): 375–388, doi:10.1007/PL00009391 <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Pach, János (2004), "Geometric graph theory", in Goodman, Jacob E.; O'Rourke, Joseph (eds.), Handbook of Discrete and Computational Geometry, Discrete Mathematics and Its Applications (2nd ed.), Chapman and Hall/CRC <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Matoušek, Jiří; Tancer, Martin; Wagner, Uli (2009), "Hardness of embedding simplicial complexes in 
 
 
 
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \mathbb {R} ^{d}}
 
", Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 855–864 <a href="/wiki/Ji%C5%99%C3%AD_Matou%C5%A1ek_(mathematician)" target="_blank">/wiki/Ji%C5%99%C3%AD_Matou%C5%A1ek_(mathematician)</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Brass, Peter (2004), "Turán-type problems for convex geometric hypergraphs", in Pach, J. (ed.), Towards a Theory of Geometric Graphs, Contemporary Mathematics, American Mathematical Society, pp. 25–33 <a href="/wiki/J%C3%A1nos_Pach" target="_blank">/wiki/J%C3%A1nos_Pach</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Dey, Tamal K.; Pach, János (1998), "Extremal problems for geometric hypergraphs", Discrete and Computational Geometry, 19 (4): 473–484, doi:10.1007/PL00009365 <a href="/wiki/Tamal_Dey" target="_blank">/wiki/Tamal_Dey</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Dey, Tamal K.; Pach, János (1998), "Extremal problems for geometric hypergraphs", Discrete and Computational Geometry, 19 (4): 473–484, doi:10.1007/PL00009365 <a href="/wiki/Tamal_Dey" target="_blank">/wiki/Tamal_Dey</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Živaljević, Rade T.; Vrećica, Siniša T. (1992), "The colored Tverberg's problem and complexes of injective functions", Journal of Combinatorial Theory, Series A, 61 (2): 309–318, doi:10.1016/0097-3165(92)90028-S <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Dey, Tamal K.; Pach, János (1998), "Extremal problems for geometric hypergraphs", Discrete and Computational Geometry, 19 (4): 473–484, doi:10.1007/PL00009365 <a href="/wiki/Tamal_Dey" target="_blank">/wiki/Tamal_Dey</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Dey, Tamal K.; Pach, János (1998), "Extremal problems for geometric hypergraphs", Discrete and Computational Geometry, 19 (4): 473–484, doi:10.1007/PL00009365 <a href="/wiki/Tamal_Dey" target="_blank">/wiki/Tamal_Dey</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">Bárány, Imre; Fürédi, Zoltán (1987), "Empty simplices in Euclidean-space", Canadian Mathematical Bulletin, 30 (4): 436–445, doi:10.4153/cmb-1987-064-1, hdl:1813/8573, S2CID 122255929 <a href="/wiki/Canadian_Mathematical_Bulletin" target="_blank">/wiki/Canadian_Mathematical_Bulletin</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Károlyi, Gyula; Solymosi, József (2002), "Almost disjoint triangles in 3-space", Discrete and Computational Geometry, 28 (4): 577–583, doi:10.1007/s00454-002-2888-z <a href="/wiki/J%C3%B3zsef_Solymosi" target="_blank">/wiki/J%C3%B3zsef_Solymosi</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
</ol>

Topological graph open-in-new

Topological graph