dc.contributor.editor | Díaz Báñez, José Miguel | es |
dc.contributor.editor | Garijo Royo, Delia | es |
dc.contributor.editor | Márquez Pérez, Alberto | es |
dc.contributor.editor | Urrutia Galicia, Jorge | es |
dc.creator | Kynčl, Jan | es |
dc.date.accessioned | 2017-05-22T07:13:21Z | |
dc.date.available | 2017-05-22T07:13:21Z | |
dc.date.issued | 2013 | |
dc.identifier.citation | Kynčl, J. (2013). Improved enumeration of simple topological graphs. En XV Spanish Meeting on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/60169 | |
dc.description.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 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. | es |
dc.description.sponsorship | Graph Drawings and Representations, EuroGIGA Project | es |
dc.description.sponsorship | Centre Interfacultaire Bernoulli | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | XV Spanish Meeting on Computational Geometry (2013), pp. 107-110. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Improved enumeration of simple topological graphs | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada II | |
dc.relation.projectID | GIG/11/E023 | es |
dc.relation.projectID | SVV-2013-267313 | es |
dc.relation.projectID | Swiss National Science Foundation | es |
dc.relation.publisherversion | http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf | es |
idus.format.extent | 4 p. | es |
dc.publication.initialPage | 107 | es |
dc.publication.endPage | 110 | es |
dc.eventtitle | XV Spanish Meeting on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |