By Emily Groves, La Trobe University

As the title suggests, my project consisted of the exploration of the drawings of the complete graphs  and , and the complete bipartite graph . An interest of such comes under the field of Topological Graph Theory.

A graph, in a sense, is a way of showing the relationship between objects (vertices) and how they connect (edges). I dealt with simple finite graph drawings in the plane, as the graphs had no multiple edges nor loops (Gross and Tucker, 2001).

As explained by Richter and Thomassen (1997), the complete graph has  vertices such that every pair is joined by an edge, and a complete bipartite graph has two sets of vertices,  and , such that each vertex in one set is joined to every vertex in the other set by edges. The common notation for a complete graph with  vertices is , and for a complete bipartite graph on sets of  and  vertices is . Figure 1 shows the clear relationship with the graph title and graph.

The idea is to deform the edges of these graphs to manipulate the number of crossings. The restriction is to not let pairs of independent edges (edges that are distinct and do not share a vertex, e.g. edges (14) and (56)) cross more than once. Adjacent edges (edges sharing a common vertex, e.g. edges (24) and (34)) can cross as many times as one likes, but these crossings are not counted. The term tolerable was given to the drawings that are good, where pairs of independent crossings occur at most once with no adjacent edges crossing, or “not-so” bad, where adjacent edges cross and independent crossings occur at most once.

I completed many drawings, where a successful drawing is tolerable. When it came to , it was very difficult to obtain successful drawings as there are tolerable drawings with independent crossings for each integer between and including 3 to 40!!  and  had tolerable drawings with independent crossings for each odd integer between and including 1 to 15 and 1 to 17, respectively. These of course were not as much of a lengthy task. These results gave a condition on the number of independent crossings that produces a tolerable drawing. For these graphs only the good drawings are well understood, so the tolerable drawings added a significant finding to the knowledge of them.

I am very proud of my drawings, so I encourage you to check them out in my report.

 

Emily Groves was a recipient of a 2018/19 AMSI Vacation Research Scholarship.

Contact Us

We're not around right now. But you can send us an email and we'll get back to you, asap.

Not readable? Change text.