Counting the Number of Crossings in a Fixed Graph Embedding in the Plane If I have a graph $G$ with each node fixed at coordinates $(x,y)$ in the plane, is there an efficient way of counting the number of crossings of the edges of the graph?
I was thinking of comparing the coordinates of every pair of edges to see if the endpoints cross, but that would be pretty inefficient for large graphs. Is there a more efficient method of computing the number of crossings?
 A: I think that you should think of this problem outside of graph theory and just think of the edges of the graph as a collection of line segments in the plane. You are going to want to use the Bentley–Ottmann algorithm for this. For $n$ line segments with $k$ crossings, it has time-complexity $\operatorname{O}\left((n + k) \log n\right)$, which beats the $\operatorname{O}(n^2)$ complexity of the "check every pair of segments" approach you described. The algorithm is intended to be used with a set of well-behaved line segments in the plane (no line segments share an endpoint, no three line segments intersect at a single point, etc), but you should be able to adapt it to use on line segments that form a graph.
The Bentley-Ottmann algorithm is an example of a sweep line algorithm where the procedure is based on the idea of a line sweeping through the plane over the objects (segments) we are interested in. The idea is that while the line is sweeping over the plane, it is iteratively sweeping over our collection of segments. We can count the number of crossing by keeping track of the order in which our segments intersect the sweep-line. If the order of the intersection points of two segments with our sweep-line switches, we know that those segments must intersect.
A more detailed description of the algorithm can be found on the Bentley-Ottmann algorithm Wikipedia page.
