Estudi de la planaritat i número de talls d’un graf

Abstract

In this project, we will work on two types of graphs, the complete and the complete bipartite graph. They are two important structures in graph theory and are defined in 1.2.1. We show the proofs for each case for which the number corresponding to the minimum cuts of edges is already known. What is more, we also explain some general lower bounds achieved for the minimum. All the proofs can be found in several original papers and our work fixes all and is a useful guide for having a general reference point. The fact that this is not a recent problem can be noticed because the first one who wrote about this was Zarankiewicz in 1954. He used only mathematical arguments like other mathematicians that in the sixties and seventies developed their own methods. In 1993, Woodall started using computational algorithms [17] and finally, Farahani in 2013 published the last paper explained in this work [2]. The last part of the project is about some algorithms we have done that generated our initial interest for this topic. Although they do not give unknown results, they are expected to open a new path that will help us to reach new objectives. To conclude, we finally see that this is an open problem and it is difficult to determinate how the improvements will come. The lasts proofs that use the computational power and have achieved better bounds fall easily with bigger graphs because this is an NP-complete problem. In my opinion, better results will arrive when we manage to reduce the number of cases limiting the huge magnitude of the problem, otherwise, there should be extremely good improvements in the actual algorithms to offset the complexity.