2
$\begingroup$

The crossing number of a graph $G$ is defined as the least number of crossings introduced when $G$ is drawn as a topological graph in the plane.

Is there anything known about the maximum number of crossings which can be introduced by drawing $G$ as a topological graph in the plane?

$\endgroup$

2 Answers 2

5
$\begingroup$

As Vinicius Santos has already said, this doesn't make sense without further restrictions (you can make any single edge cross itself as many times as you like). But a well-studied variant of this arises if you only allow each pair of edges to cross at most once, and not at all if they share an endpoint. Then, the graph drawings in which every possible crossing exists are called thrackles, and it's a longstanding open problem to characterize them.

$\endgroup$
2
$\begingroup$

I don't think this value is well defined the way it was posed, since there is always a drawing where an edge cross every other, but if you restrict the problem to linear drawings, then you have the maximum linear crossing number. This page of Douglas West relates this parameter with other parameters involving crossings. I think it can be useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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