The main results of this dissertation show evidence supporting the Successive Surface Scaffolding Conjecture. This is a new conjecture that, if true, guarantees the existence of all the wye-delta-order minimal obstructions of a surface S as subgraphs of the irreducible triangulations of the surface S with a crosscap added. A new data structure, i.e. an augmented rotation system, is presented and used to create an exponential-time algorithm for embedding graphs in any surface with a constant-time check of the change in genus when inserting an edge. A depiction is a new formal definition for representing an embedding graphically, and it is shown that more than one depiction can be given for nonplanar embeddings, and that sometimes two depictions for the same embedding can be drastically different from each other. An algorithm for finding the essential cycles of an embedding is given, and is used to confirm for the projective-plane obstructions, a theorem that shows any embedding of an obstruction must have every edge in an essential cycle. Obstructions of a general surface S that are minor-minimal and not double-wye-delta-minimal are shown to each have an embedding on the surface S with a crosscap added. Finally, open questions for further research are presented. / Graduate

<p dir="ltr">This dissertation introduces a novel graph embedding paradigm, leveraging a force-directed scheme for graph embedding. In the field of graph embedding, an "embedding" refers to the process of transforming elements of a graph such as nodes, or edges, or potentially other structural information of the graph into a low-dimensional space, typically a vector space, while preserving the graph's structural properties as much as possible. The dimensions of the space are supposed to be much smaller than the elements of the graph that are to be embedded. This transformation results in a set of vectors, with each vector representing a node (or edge) in the graph. The goal is to capture the essence of the graph's topology, node connectivity, and other relevant features in a way that facilitates easier processing by machine learning algorithms, which often perform better with input data in a continuous vector space.</p><p dir="ltr">The main premise of kinematics-based force-directed graph embedding is that the nodes are considered as massive mobile objects that can be moved around in the embedding space under force. In this PhD thesis, we devised a general theoretical framework for the proposed graph embedding paradigm and provided the mathematical proof of convergence given the required constraints. From this point on, the objective was to explore force functions and parameters and methods of applying them in terms of their efficacy regarding graph embedding applications. We found some force functions that outperformed the state-of-the-art methods.</p><p dir="ltr">The author of this manuscript believes that the proposed paradigm will open a new chapter, specifically in the field of graph embedding and generally in the field of embedding.</p>

This Master Thesis deals with the drawing algorithms of graphs known from the mathematical theory. These algorithms deals with an appropriate distribution of the graph vertices in order to obtain the most clear and readable graphs for human readers. The main objective of this work was also to implement the drawing algorithm in the application that would allow to edit the graph. This work deals also with graphs representation in computers.