GUI Application to Setup Simple Graph on the Plane using Tkinter of Python

Abstract

In graph theory, drawing a simple graph on the plane might result an intersection of pair of edges that is not intended as a vertex called crossing. The least amount of crossing in any simple drawing of a graph is the crossing number of that graph, 𝑐𝑟(𝐺). Given a graph G and an integer 𝐾, the general problem to proof 𝑐𝑟(𝐺) ≤ 𝐾 is an NP-Complete problem, which means, it is likely intractable. One of the way to proof 𝑐𝑟(𝐺) ≤ 𝐾 is by showing the drawing of graph 𝐺 with 𝐾 number of crossing; doing it with a computer application can be much of help. Therefore, the purpose of our research is to create one using Tkinter of Python. The development of the application is feature driven. The developed features are used to find any simple drawing of graphs on the plane. As the result, the application can proof 𝑐𝑟(𝐾_3,3) ≤ 1, 𝑐𝑟(𝐾_6) ≤ 3, and 𝑐𝑟(𝐾𝐺_5,2) ≤ 2.