Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654409 | European Journal of Combinatorics | 2009 | 10 Pages |
A simple topological graph T=(V(T),E(T))T=(V(T),E(T)) is a drawing of a graph in the plane, where every two edges have at most one common point (an end-point or a crossing) and no three edges pass through a single crossing. Topological graphs GG and HH are isomorphic if HH can be obtained from GG by a homeomorphism of the sphere, and weakly isomorphic if GG and HH have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on nn vertices is 2Θ(n4)2Θ(n4). We also show that the number of weak isomorphism classes of simple complete topological graphs with nn vertices and n4 crossings is at least 2n(logn−O(1))2n(logn−O(1)), which improves the estimate of Harborth and Mengersen.