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}}):
DrawGraph(G1)
DrawGraph(G1,style=planar)

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);
DrawGraph(K5);
vp:=[[-1,0],[1,0],[-0.2,0.5],[0.2,0.5],[0,1]];
SetVertexPositions(K5,vp);  #modified the vertex position

DrawGraph(K5);

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:

https://de.maplesoft.com/products/maple/new_features/Maple2020/graphtheory.aspx

https://de.maplesoft.com/support/help/Maple/view.aspx?path=GraphTheory/SetVertexPositions

I think the software can improve some calculations related to topological graph theory, such as crossing number of graph, etc.

 

Please Wait...