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).$

  • $\begingroup$ According to the definition, $pcr(G)\leq cr(G)$, however, it is not unknown whether $pcr(G)=cr(G)$. $\endgroup$ – Rupei Xu Apr 28 '15 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$ – Rupei Xu May 11 '15 at 7:56

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.

| cite | improve this answer | |
  • $\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$ – Rupei Xu Apr 28 '15 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 Apr 28 '15 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.