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

ABSTRACT

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.

REFERENCES

• 1: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: J. Edmonds, "A Combinatorial Representation for Polyhedral Surfaces", Amer. Math. Soc. Notices, 7 (1960), 646.
• 4: I. S. Filotti, An efficient algorithm for determining whether a cubic graph is toroidal, Proceedings of the tenth annual ACM symposium on Theory of computing, p.133-142, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804341]
• 5: I. S. Filotti, "An Algorithm for Imbedding Cubic Graphs in the Torus", J.C.S.S. (to appear).
• 6: P. Giblin, "Graphs, Surfaces and Homology - An Introduction to Algebraic Topology", Chapman and Hall, London, U.K., 1977.
• 7: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 8: W. Massey, "Algebraic Topology: An Introduction", Harcourt, Brace and World Inc., New York, New York, 1967.
• 9: G. Miller, "Poincaré Intersection Numbers and Some Applications"(to appear).
• 10: J. Reif, "A Note on the Complexity of Imbedding Extension Problems" (to appear).
• 11: J. Reif, "Polynomial Time Recognition of Graphs of Fixed Genus" (to appear).
• 12: A. White, "Graphs, Groups and Surfaces", North-Holland Publishing Co., American Elsevier Co., New York, New York, 1973.
• 13: M. Garey, D. Johnson, G. Miller, C. Papadimitriou, "Circular Arc Coloring and Related Problems" to appear.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory