Enumeration of simple complete topological graphs

Abstract

We prove that the number of isomorphism classes of simple complete topological graphs on n vertices is 2^{\Theta(n^4)}. We also show that the number of weak isomorphism classes of simple complete topological graphs with n vertices and n choose 4 crossings is at least 2^(n(log n-O(1))), which improves the estimate of Harborth and Mengersen.

Keywords

• Enumeration
• simple
• complete
• topological
• graphs