Planar Crossing Numbers of Graphs of Bounded Genus

Autor:	Imrich Vrto, Hristo N. Djidjev
Rok vydání:	2012
Předmět:	Discrete mathematics Constructive Graph Theoretical Computer Science Combinatorics Constant factor Planar Computational Theory and Mathematics Bounded function Discrete Mathematics and Combinatorics Geometry and Topology Crossing number (graph theory) Time complexity Mathematics
Zdroj:	Discrete & Computational Geometry. 48:393-415
ISSN:	1432-0444 0179-5376
DOI:	10.1007/s00454-012-9430-8
Popis:	Pach and Toth proved that any n-vertex graph of genus g and maximum degree d has a planar crossing number at most c g dn, for a constant c>1. We improve on this result by decreasing the bound to O(dgn), and also prove that our result is tight within a constant factor. Our proof is constructive and yields an algorithm with time complexity O(dgn). As a consequence of our main result, we show a relation between the planar crossing number and the surface crossing number.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::cac613a12bfe1d202b7c4c587c038624 https://doi.org/10.1007/s00454-012-9430-8 Zobrazit plný text záznamu Full text from SpringerLink