<p>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 href="http://en.wikipedia.org/wiki/Conway%27s_thrackle_conjecture">a longstanding open problem</a> to characterize them.</p>

CC BY-SA 3.0
2012-09-15T05:54:35.243Z
2012-09-15T05:54:35.243Z
David Eppstein
<p>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. <a href="http://www.math.uiuc.edu/~west/regs/crossnum.html" rel="nofollow">This page of Douglas West</a> relates this parameter with other parameters involving crossings. I think it can be useful.</p>

CC BY-SA 3.0
2012-09-15T03:59:19.100Z
2012-09-15T03:59:19.100Z
Vinicius dos Santos
<p>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.</p>

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

<graph-theory><cg.comp-geom><planar-graphs><graph-drawing>
Maximum Crossing number of topological graph
101011
# Maximum Crossing number of topological graph

(Asked by: username_0 on 2012-09-14)

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?

**Tags:** graph-theory, cg.comp-geom, planar-graphs, graph-drawing

---

## 2 answers

### Answer by username_1 on 2012-09-15. Score: 5 | Accepted answer

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](http://en.wikipedia.org/wiki/Conway%27s_thrackle_conjecture) to characterize them.


---

### Answer by username_2 on 2012-09-15. Score: 2

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](http://www.math.uiuc.edu/~west/regs/crossnum.html) relates this parameter with other parameters involving crossings. I think it can be useful.


---

