Pfaffian Graphs: Properties and Algorithms

• Grant number: 24/02636-4
• Support Opportunities: Scholarships in Brazil - Master
• Start date: November 01, 2024
• End date: July 31, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cláudio Leonardo Lucchesi
• Grantee: Guillermo Enrique Junchaya Heredia
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

The subject, Pfaffian Graphs, has applications in econometrics and in the analysis of the stability of organic compounds. From a theoretical point of view, the subject is quite attractive, with interesting algorithms and open problems. Currently, characterizations of Pfaffian graphs and the corresponding efficient algorithms are known only for bipartite and near-bipartite graphs. The objective of the Master's dissertation is to present the state of the art, with the description of theorems and efficient algorithms, in addition to the citation of some of the most important applications.