On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)

摘要

In this paper we present an algorithm which on input a graph G and a positive integer g finds an embedding of G on a surface on genius g, if such an embedding exists. This algorithm runs in (v) O(g) steps where v is the number of vertices of G.

We believe that removing the nondiscrete topological definitions (i.e., the notation or differentiability, 2-dimensional surface, etc.) from our formal definitions has a multitude of advantages. First our goal is to produce an algorithm which operates on discrete machines and thus at some point we must remove these notions anyway. Secondly, demonstrations on proofs in the amalgam of graph theory and topology have been riddled with flaws (e.g., 4-color theorem, planarity algorithms, Jordan curve theorem), and which, no doubt, this paper also suffers. The hope is that a combinatorial proof may transcend these problems. Third, our main goal is not just to draw graphs on "inner tubes" but to understand how graph theory, topology and computational complexity interact. We have kept no definitions sacred and we have redefined the notion of a graph. We have even rewritten Euler's formula.