This question was inspired by the game Planarity in which a player tries to position the vertices so that no two lines cross. As I move the vertices, the change in the number of crossings is detected in time. It is also necessary for my research in graph drawing.
In Mathematica, we can draw a graph.
Problem 1. How can we detect the number of crossings in the layout of a graph?
For example, we have the following graph with LayeredDigraphEmbedding; how do we detect the number of crossings? The graph I am considering can contain curves.
Graph[{1 \[UndirectedEdge] 16, 1 \[UndirectedEdge] 19,
2 \[UndirectedEdge] 13, 2 \[UndirectedEdge] 14,
2 \[UndirectedEdge] 15, 2 \[UndirectedEdge] 16,
2 \[UndirectedEdge] 19, 3 \[UndirectedEdge] 6,
3 \[UndirectedEdge] 9, 3 \[UndirectedEdge] 10,
3 \[UndirectedEdge] 17, 3 \[UndirectedEdge] 20,
4 \[UndirectedEdge] 7, 4 \[UndirectedEdge] 13,
4 \[UndirectedEdge] 15, 4 \[UndirectedEdge] 20,
5 \[UndirectedEdge] 10, 6 \[UndirectedEdge] 16,
7 \[UndirectedEdge] 8, 7 \[UndirectedEdge] 9,
7 \[UndirectedEdge] 18, 8 \[UndirectedEdge] 13,
8 \[UndirectedEdge] 19, 9 \[UndirectedEdge] 15,
9 \[UndirectedEdge] 17, 11 \[UndirectedEdge] 18,
12 \[UndirectedEdge] 20, 13 \[UndirectedEdge] 14,
13 \[UndirectedEdge] 18, 13 \[UndirectedEdge] 19,
14 \[UndirectedEdge] 17, 15 \[UndirectedEdge] 18,
15 \[UndirectedEdge] 19, 16 \[UndirectedEdge] 19,
17 \[UndirectedEdge] 18}, GraphLayout -> "LayeredDigraphEmbedding"]
I find 26 crossings by hand.
Problem 2. Given an edge, how do we determine which edges cross it?
For example:
Graph[{1 \[UndirectedEdge] 16, 1 \[UndirectedEdge] 19,
2 \[UndirectedEdge] 13, 2 \[UndirectedEdge] 14,
2 \[UndirectedEdge] 15, 2 \[UndirectedEdge] 16,
2 \[UndirectedEdge] 19, 3 \[UndirectedEdge] 6,
3 \[UndirectedEdge] 9, 3 \[UndirectedEdge] 10,
3 \[UndirectedEdge] 17, 3 \[UndirectedEdge] 20,
4 \[UndirectedEdge] 7, 4 \[UndirectedEdge] 13,
4 \[UndirectedEdge] 15, 4 \[UndirectedEdge] 20,
5 \[UndirectedEdge] 10, 6 \[UndirectedEdge] 16,
7 \[UndirectedEdge] 8, 7 \[UndirectedEdge] 9,
7 \[UndirectedEdge] 18, 8 \[UndirectedEdge] 13,
8 \[UndirectedEdge] 19, 9 \[UndirectedEdge] 15,
9 \[UndirectedEdge] 17, 11 \[UndirectedEdge] 18,
12 \[UndirectedEdge] 20, 13 \[UndirectedEdge] 14,
13 \[UndirectedEdge] 18, 13 \[UndirectedEdge] 19,
14 \[UndirectedEdge] 17, 15 \[UndirectedEdge] 18,
15 \[UndirectedEdge] 19, 16 \[UndirectedEdge] 19,
17 \[UndirectedEdge] 18}, GraphLayout -> "LayeredDigraphEmbedding",
VertexLabels -> Placed[Automatic, Center], VertexSize -> 0.25]
We can find that the edge $\{4, 13\}$ is crossed $3$ times in total and it was crossed by $\{3,9\}, \{3,17\}, \{8,19\}$, respectively.
It feels like it is involved in computational geometry.