Question: layouts about DrawGraph

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.

G1:=AddEdge( CycleGraph([v__1,v__2,v__3,v__4]),{{v__2,v__4},{v__1,v__3}}):

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.


Please Wait...