4
$\begingroup$

A common point of two edges in a graph drawing that is not an incident vertex is called a crossing.

The crossing number $cr(G)$ is defined to be the minimum number of crossings in any drawing of $G$.

The pairwise crossing number of $G$, denoted with $pcr(G)$, is the minimum number of pairs of edges $(e_1, e_2) \in E \times E$, $e_1 \neq e_2$ such that $e_1$ and $e_2$ determine at least one crossing, over all drawings of $G$.

Can you give an example to show pairwise crossing number is not equal to crossing number? i.e. $pcr(G)\neq cr(G).$

Improve this question
$\endgroup$
2
  • $\begingroup$ According to the definition, $pcr(G)\leq cr(G)$, however, it is not unknown whether $pcr(G)=cr(G)$. $\endgroup$
    – user39815
    Commented Apr 28, 2015 at 15:12
  • $\begingroup$ Surprisingly, I just noticed that In 1995, in the Open Problem session of the AMS Conference on Topological Graph Theory, Bojan Mohar posted the problem of whether $cr(G)=pcr(G)$ for all $G$. Kratochvıl and Matousek shows that in general, given a drawing, it need not be possible to eliminate multiple crossings of pairs without introducing new crossing pairs.Existing results are mainly on estimating the upper bound of $cr(G)$ using $pcr(G).$ But in general, it is still open. $\endgroup$
    – user39815
    Commented May 11, 2015 at 7:56

1 Answer 1

Reset to default
5
$\begingroup$

As far as I know this is still an open problem. It is listed as an open problem in the paper Which crossing-number is it anyway? by Pach and Tóth, and also in the introduction of this more recent survey by Schaefer. Indeed, Schaefer notes that some authors define the crossing number as the pair crossing number, which can lead to immense confusion, and sometimes incorrect arguments. Even though the two parameters may be equal for all graphs, one cannot transpose the notions while writing a proof.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the references. I wonder why such examples is hard to find. I tried it with some graph drawing softwares, but it seems not much helpful hints. $\endgroup$
    – user39815
    Commented Apr 28, 2015 at 17:34
  • 3
    $\begingroup$ The simple answer is that both parameters are very hard to complete exactly (NP-hard). We don't even know the crossing number exactly for very simple classes of graphs (like the complete graphs). $\endgroup$
    – Tony Huynh
    Commented Apr 28, 2015 at 18:05

You must log in to answer this question.