0
$\begingroup$

Crossing number$($cr$)$: The crossing number of a simple graph is the minimum number of crossings that can occur when this graph is drawn in the plane where no three arcs representing edges are permitted to cross at the same point. For an undirected simple graph $G$ with $n$ vertices and $e$ edges such that $e > 7n$ the crossing number is always at least $$cr(G)\geq \frac{e^3}{29n^2}$$

$(1)$ I was wondering is there exist any upper bound in general$?$ Here is a upper bound for the crossing number of the complete bipartite graph $K_{m,n}$. I need a proof of that result.$($if possible than provide a simple's one$)$

Thickness: The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union.

$(2)$ I was wondering is there any relation between these two number$?$
I asked the same question at MSE and get suggested to ask it here.

Improve this question
$\endgroup$
6
  • $\begingroup$ you can find details on the crossing number of $K_n$ in e.g. arxiv.org/abs/1309.3665v2 $\endgroup$
    – Dima Pasechnik
    Commented Nov 20, 2019 at 14:53
  • $\begingroup$ I will definitely look your given resource @DimaPasechnik $\endgroup$
    – Emon Hossain
    Commented Nov 20, 2019 at 14:57
  • 1
    $\begingroup$ basically, for $K_n$ there are explicit drawings known, which provide you an upper bound on the crossing number. The lower bound is still conjectural. $\endgroup$
    – Dima Pasechnik
    Commented Nov 20, 2019 at 14:58
  • $\begingroup$ Perhaps the world’s expert on crossing numbers is Gelasio Salazar ... google him, all his papers (a ton of groundbreaking results) are (were) available on his university website $\endgroup$
    – EGME
    Commented Nov 20, 2019 at 18:21
  • 1
    $\begingroup$ the one I linked is one of Gelasio’s papers :) $\endgroup$
    – Dima Pasechnik
    Commented Nov 20, 2019 at 19:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .