I've been studying the drawing of graph lately . One of the themes is 1-planar graph .
A 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.
I know it is NP hard to determine whether a graph is a 1-planar . My idea is to take advantage of some mathematical software to provide some roughly and intuitive understanding before determining .
Now, the layout of vertices or edges becomes important. The drawing of a plane graph is a good example.
By Kuratowski's or Wagner's theorems, K5 is not planar graph, But is it 1 planar graph? I modified the vertex position of the graph and found a 1-plane drawing.
K5 := CompleteGraph(5);
SetVertexPositions(K5,vp); #modified the vertex position
My problem is that I see that Maple2020 has updated a lot of layouts about DrawGraph graph theory backpack , and I don’t know which ones are working towards the least possible number of crossing of each edges of graph .
Some links that may be useful:
I think the software can improve some calculations related to topological graph theory, such as crossing number of graph, etc.