Ponencia
Improved enumeration of simple topological graphs
Autor/es | Kynčl, Jan |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-05-22 |
Publicado en |
|
Resumen | 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 endpoint or a crossing) and no three edges pass through a single crossing. Topological ... 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 endpoint 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 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 with n vertices, m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize G is at most 2 O(n2log(m/n)), and at most 2O(mn1/2 log n) if m ≤ n 3/2. As a consequence we obtain a new upper bound 2 O(n3/2 log n) on the number of intersection graphs of n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with n vertices to 2n2 ·α(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 is at most 2 m2+O(mn) and at least 2 Ω(m2) for graphs with m > (6 + ε)n. |
Identificador del proyecto | GIG/11/E023
SVV-2013-267313 Swiss National Science Foundation |
Cita | Kynčl, J. (2013). Improved enumeration of simple topological graphs. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Improved enumeration of simple ... | 660.2Kb | [PDF] | Ver/ | |