The study of graph drawings on surfaces traces its origins to the 19th century, notably through the Four Colour Problem and the Heawood Map Colouring Problem. These problems inspired extensive research into the relationship between graphs and the surfaces they can be drawn on. A surface is characterized by its orientability (orientable or nonorientable) and by its genus. The sphere is the orientable surface with genus 0 and is denoted by S_0. The orientable surface of genus g, denoted by S_g, is obtained by adding g handles to the sphere, while the nonorientable surface of genus g ̅, denoted by N_g ̅ , is obtained by adding g ̅ crosscaps (or Möbius bands) to the sphere.

For a graph G, the crossing number of G on a given surface is the least number of crossings between the edges of G among all the possible drawings of G on that surface. A graph is embeddable on a surface if it can be drawn without any edge crossings. The genus of G is the smallest genus of a surface that allows an embedding of G. These concepts lead to two complementary perspectives that can be considered when drawing graphs on surfaces, namely fixing the surface and determining the crossing number of graphs drawn on that surface, or fixing the graph and determining the surface with smallest genus that allows an embedding of that graph.

Both problems – computing the crossing number of a graph and determining the (orientable and nonorientable) genus of a graph – are known to be NP-complete. Despite this complexity, a lot of work was done and significant progress has been made in determining these values for various families of graphs.

In this talk, we present both classical and recent results on the crossing number and the genus of graphs, highlighting the key techniques used to prove these results.

Prof. John Baptist Gauci is currently a resident associate professor at the Department of Mathematics within the Faculty of Science at the University of Malta. He started his employment with the University of Malta in 2006 as a visiting lecturer and since then he has been involved in the design, delivery and evaluation of various mathematical courses within the department. He has also taught various mathematical and statistical courses at different levels at the Malta College of Arts, Science and Technology (MCAST) between 2002 and 2012, where he also served as the Mathematics’ Subject Coordinator for two years. Over the years, John has been appointed on various national boards tasked with the setting up, revising and evaluating aspects related to the teaching, learning and assessment of mathematics in Malta.

John obtained his Bachelor’s Degree in Education specialising in mathematics in 1999 from the University of Malta. Between 1999 and 2002, while teaching on a full-time basis at a secondary school, he read for a Master of Science degree in mathematics in the area of combinatorics and graph theory with the same university under the supervision of Prof. Stanley Fiorini. In 2009 he obtained his PhD degree from the University of Reading, U.K., under the supervision of Prof. Anthony J.W. Hilton. 

Over the past years, John has been invited by various universities to deliver research talks and short courses, including universities in Italy, Slovenia and Turkey. He regularly attends and delivers talks in international mathematical conferences and has been invited to attend specialised workshops in crossing numbers and other topics, including workshops organised under the Banff International Research Station (BIRS) programs in Canada. He has supervised numerous undergraduate, masters and doctoral dissertations and has published over 35 papers in international peer-reviewed journals. He was the main organiser of two international conferences in combinatorics, graph theory and combinatorial optimisation, namely the “Second Malta Conference in Graph Theory and Combinatorics (2MCGTC-2017)” and the “ECCO XXXII Conference of the European Chapter on Combinatorial Optimization (2019)”. He has also served as the guest editor for the journal “Discrete Applied Mathematics” (2019), the “Journal of Combinatorial Optimisation” (2021) and the journal “Mathematics” (2025). 

John’s main research interests revolve around topological graph theory, in particular problems involving the genus and the crossing number of graphs. However, he has worked in other areas, including k-to-1 functions between graphs (which was the research topic of his doctoral dissertation); problems in structural graph theory, including connectivity, diameter vulnerability, Hamiltonicity and matching problems; and spectral properties of graphs, in particular problems on the nullity of graphs.