I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.
I am randomly creating a path thru all the vertices and I want to know if there is any efficient way to find all the intersections on my path.
A path of length $n$ consists of $n$ line segments in the plane. You want to find all intersections between these line segments. This is a standard problem that has been studied in depth in the computer graphics literature.
A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric algorithm). The running time of this algorithm is $O(n^2)$. In terms of worst-case complexity, this is the best we can hope for, as in the worst case, there can be $\Theta(n^2)$ intersections, so obviously it'll take at least $\Theta(n^2)$ time to output them all.
However, in many cases, we have an arrangement of line segments where there are only a few intersections, say at most $O(n)$ intersections. In this case, there are algorithms whose running time is $O(n \lg n)$. See, e.g., the sweep line technique; there are others as well. In general, if there are $k$ intersections, the total running time for the sweep line algorithm to find all $k$ intersections is $O((n+k) \lg n)$ time.
