lcz

260 Reputation

6 Badges

1 years, 282 days

MaplePrimes Activity


These are questions asked by lcz

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)

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.

 

I'm thinking of better demonstrating the cartesian product of a graph.
With the help documentation, we can easily find the cartesian product of two graphs.

with(GraphTheory):
G := CycleGraph([v__1,v__2,v__3,v__4]);
H:=Graph({{u__1,u__2}}):
DrawGraph(G,size=[250,250],stylesheet=[vertexborder=false,vertexpadding=10,edgecolor = "Red",
vertexcolor="navy",edgethickness=3]);
DrawGraph(H,size=[250,250],stylesheet=[vertexborder=false,vertexpadding=10,edgecolor = "Blue",
vertexcolor="Gold",edgethickness=3]);


GH:=CartesianProduct(G,H)
DrawGraph(GH,style=spring)