Embedding graphs on surfaces is a widely studied topic in mathematics. Initially, planar graphs, which are graphs embedded on the plane or sphere, were the primary focus. Following Kuratowski's work in 1930, attention shifted to graphs cellular embedded in orientable surfaces of higher genus. Despite significant advancements in understanding the cellular embedding possibilities of abstract graphs, the cellular embeddability of spatial graphs remained less explored.
During my PhD, I studied the cellular embedding possibilities of spatial graphs when the surface needs to be embedded in 3-space up to ambient isotopy, a setting highly relevant for applications in the three-dimensional Euclidean world.
For example, one of the chemical applications is a procedure called DNA origami self-assembly. The complementary sequences forming the two strands of DNA and its robustness make it a perfect building material. Because of this reason, bioengineers use DNA for building complex nanostructures. Among the uses of this procedure are the synthesis of vaccines and the accurate positioning of components on nanoelectronic circuits.
Thanks to work of Ellis-Monaghan et al. (2017), the scaffolding necessary for DNA origami to build graph-like structures can easily be found if the graph is cellular embedded on a surface in 3-space.
Motivated by mathematics and science in general, my thesis introduces leveled spatial graphs and explores their cellular embedding possibilities. It demonstrates that every leveled embedding with up to four levels can be cellular embedded and provides a construction for the surface where the spatial graph embeds, along with a formula to compute the genus of the surface. An algorithm is also presented to build a surface for all leveled spatial graph, discussing its limitations.
Further, the thesis places leveled spatial graphs within the broader context of topological graph theory. I compare leveled embeddings with other spatial graph properties such as freeness and paneledness. A spatial graph is free if the complement of a neighborhood of the graph in 3-space has a fundamental group that is isomorphic to a cyclic group. I show in my thesis that all leveled spatial graphs are free.
A spatial graph is paneled if, for every closed path in the graph, it is possible to find a disk whose interior does not intersect the graph. I give sufficient conditions for a leveled spatial graph to be paneled, but I show that there exist paneled spatial graphs which are not leveled and vice versa.
I also introduce a new graph invariant called the level number. This invariant measures how far a spatial graph is from being planar. The research characterizes the level number of complete graphs and complete bipartite graphs.
In a parallel project, I studied a special case of leveled spatial graphs: polyhedra. I investigated local symmetry-preserving operations on polyhedra, which are operations that transform a polyhedron into another one having more edges but at least as many symmetries. In particular, I focused my attention on local symmetry-preserving operations which increased the symmetries of polyhedra. In my thesis, I provide solutions for Goldberg-Coxeter operations and local symmetry-preserving operations with inflation factors up to 6, identifying the genera in which they can increase symmetry. This work was completed during my research visit in Ghent, Belgium.
Additionally, in my thesis I compare two well-known graph operations: the line graph and the edge-complement graph. The latter builds a new graph which has the same vertices of the original one but edges only where the original did not. The former builds a new graph which has a vertex for each edge of the original one and two vertices are connected if the corresponding edges of the original graph where attached to the same vertex. I listed the properties of these operations and showed that only two graphs up to isomorphism have isomorphic line graph and edge-complement graph, offering an alternative proof to the original one by Aigner (1969).
Fabio Buccoliero will be defending his PhD thesis on 3 April 2025 at 11:45 in the Aula of the VU Amsterdam.