3
$\begingroup$

The crossing number $cr(G)$ of a graph $G$ is the lowest number of edge crossings of a plane drawing of the graph $G$. The local crossing number of a drawing of a graph is the largest number of crossings on a single edge. The minimum local crossing in any drawing of a graph is the local crossing number for that graph.

I am looking for examples $G$ so that

  • $G$ has local crossing number $k$;
  • Any drawing of $G$ with local crossing number $k$ has more crossings then $cr(G)$,

especially for $k$ is small.

Can anyone find such examples? I believe that they exist.

$\endgroup$
2
  • $\begingroup$ Florian Lehner gave a nice example for $k=1$. Next, is there any example for $k=2$. $\endgroup$
    – Xin Zhang
    Commented Jul 28, 2020 at 2:54
  • 1
    $\begingroup$ Couldn't you just replace every edge in my example by two parallel edges (or by two paths if you prefer simple graphs)? $\endgroup$ Commented Jul 28, 2020 at 8:48

1 Answer 1

5
$\begingroup$

I think the following graph works for $k = 1$:

example

It clearly has crossing number at most $2$ and local crossing number $1$.

In any drawing with $2$ or fewer crossings, the green cycles cannot cross (the spokes from the red vertices would create at least one additional crossing). Once we have embedded the green cycles and the black matching edges between them, each face meeting the "outside" of the green cycles is incident to at most two vertices of each cycle. Consequently, embedding a red vertex outside its cycle creates at least $3$ crossings (the spokes to the vertices not incident to the face where it was embedded). So the red vertices must be embedded inside their respective green cycles and thus the red edge crosses both green cycles.

I think this even shows that the drawing on the left is (up to isomorphism) the unique drawing with two crossings.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .