Toroidal grid minors and stretch in embedded graphs

DC FieldValueLanguage
dc.contributor.authorChimani, Markus
dc.contributor.authorHlineny, Petr
dc.contributor.authorSalazar, Gelasio
dc.date.accessioned2021-12-23T16:15:45Z-
dc.date.available2021-12-23T16:15:45Z-
dc.date.issued2020
dc.identifier.issn00958956
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/11572-
dc.description.abstractWe investigate the toroidal expanse of an embedded graph G, that is, the size of the largest toroidal grid contained in G as a minor. In the course of this work we introduce a new embedding density parameter, the stretch of an embedded graph G, and use it to bound the toroidal expanse from above and from below within a constant factor depending only on the genus and the maximum degree. We also show that these parameters are tightly related to the planar crossing number of G. As a consequence of our bounds, we derive an efficient constant factor approximation algorithm for the toroidal expanse and for the crossing number of a surface-embedded graph with bounded maximum degree. (C) 2019 Elsevier Inc. All rights reserved.
dc.description.sponsorshipGerman Research Foundation (DFG)German Research Foundation (DFG) [CH 897/2-1, CH 897/2-2]; Czech Science FoundationGrant Agency of the Czech Republic [14-03501S, 17-00837S]; CONACYTConsejo Nacional de Ciencia y Tecnologia (CONACyT) [106432]; Supported by the German Research Foundation (DFG), projects CH 897/2-1 and CH 897/2-2.; Supported by the Czech Science Foundation, projects 14-03501S (until 2016) and 17-00837S.; Supported by CONACYT Grant 106432.
dc.language.isoen
dc.publisherACADEMIC PRESS INC ELSEVIER SCIENCE
dc.relation.ispartofJOURNAL OF COMBINATORIAL THEORY SERIES B
dc.subjectCompact surfaces
dc.subjectCrossing number
dc.subjectCYCLES
dc.subjectDISJOINT PATHS
dc.subjectEdge-width
dc.subjectGraph embeddings
dc.subjectMathematics
dc.subjectPLANAR CROSSING NUMBERS
dc.subjectStretch
dc.subjectToroidal grid
dc.titleToroidal grid minors and stretch in embedded graphs
dc.typejournal article
dc.identifier.doi10.1016/j.jctb.2019.05.009
dc.identifier.isiISI:000503324900011
dc.description.volume140
dc.description.startpage323
dc.description.endpage371
dc.contributor.orcid0000-0003-2125-1514
dc.contributor.researcheridF-1127-2011
dc.identifier.eissn10960902
dc.publisher.place525 B ST, STE 1900, SAN DIEGO, CA 92101-4495 USA
dcterms.isPartOf.abbreviationJ. Comb. Theory Ser. B
dcterms.oaStatusGreen Submitted
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

8
Last Week
1
Last month
1
checked on Jul 16, 2024

Google ScholarTM

Check

Altmetric