首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Enumeration of simple complete topological graphs
Institution:1. Department of Computer Science, University of Texas at Dallas, 800 West Campbell Road Richardson, TX 75080, USA;2. Department of Applied Mathematics II, University of Seville, Camino de los Descubrimientos s/n, Seville 41092, Spain
Abstract:A simple topological graph 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 G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G and H have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on n vertices is 2Θ(n4). We also show that the number weak isomorphism classes of simple complete topological graphs with n vertices and (n4) crossings is at least 2n(logn?O(1)), which improves the estimate of Harborth an Mengersen.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号