Improved Enumeration of Simple Topological Graphs.

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 endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs $$G$$ G and $$H$$ H are isomorphic if $$H$$ H can be obtained from $$G$$ G by a homeomorphism of the sphere, and weakly isomorphic if $$G$$ G and $$H$$ H have the same set of pairs of crossing edges. We generalize results of Pach and Tóth and the author’s previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph $$G$$ G with $$n$$ n vertices, $$m$$ m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize $$G$$ G is at most $$2^{O(n^2\log (m/n))}$$ 2 O ( n 2 log ( m / n ) ) , and at most $$2^{O(mn^{1/2}\log n)}$$ 2 O ( m n 1 / 2 log n ) if $$m\le n^{3/2}$$ m ≤ n 3 / 2 . As a consequence we obtain a new upper bound $$2^{O(n^{3/2}\log n)}$$ 2 O ( n 3 / 2 log n ) on the number of intersection graphs of $$n$$ n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with $$n$$ n vertices to $$2^{n^2\cdot \alpha (n)^{O(1)}}$$ 2 n 2 · α ( n ) O ( 1 ) , using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize $$G$$ G is at most $$2^{m^2+O(mn)}$$ 2 m 2 + O ( m n ) and at least $$2^{\Omega (m^2)}$$ 2 Ω ( m 2 ) for graphs with $$m>(6+\varepsilon )n$$ m > ( 6 + ε ) n . [ABSTRACT FROM AUTHOR]