Crossing Number vs. Pairwise Crossing number of graphs

The crossing number of a graph $G$, $\crs(G)$ is the minimum number of intersections among edges over all possible drawings on a plane. The pairwise crossing number $\pcr(G)$ is the minimum number of pairs of edges that cross at least once over drawings. In the first part of this survey, we deal with the conjecture that $\pcr(G)=\crs(G)$, and prove that this is true for 4-edge weighted maps on annulus. Moreover, we develop methods for solving analogous $n$-edge problems including the classification of permutations on a circle. In the second part, we define the generalized crossing number $\crs_i(G)$ as the crossing number of a graph on the orientable surface of genus $i$. The crossing sequence is defined as $(\crs_i(G))_{i=0}^{g(G)}$, where $g(G)$ is the genus of the graph. This part aims at the conjecture that for each sequence of 4 numbers decreasing to 0, there is some graph with such numbers as its crossing sequence. We come up with a particular family of graphs which have concave crossing sequences of length 4, but partially prove it.

Event Topic

Discrete Applied Math Seminar