Document
Journal of Combinatorial Theory. Series B
Generically Dependent Continuant
RDF description of Toroidal grid minors and stretch in embedded graphs - http://orbis.uaslp.mx/vivo/individual/scopus6588
Article
Information Content Entity
Compact surfaces; Crossing number; Edge-width; Graph embeddings; Stretch; Toroidal grid
We 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. © 2019 Elsevier Inc.
Toroidal grid minors and stretch in embedded graphs