Toroidal grid minors and stretch in embedded graphs

Autor(en): Chimani, Markus 
Hlineny, Petr
Salazar, Gelasio
Stichwörter: Compact surfaces; Crossing number; CYCLES; DISJOINT PATHS; Edge-width; Graph embeddings; Mathematics; PLANAR CROSSING NUMBERS; Stretch; Toroidal grid
Erscheinungsdatum: 2020
Herausgeber: ACADEMIC PRESS INC ELSEVIER SCIENCE
Enthalten in: JOURNAL OF COMBINATORIAL THEORY SERIES B
Band: 140
Startseite: 323
Seitenende: 371
Zusammenfassung: 
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. (C) 2019 Elsevier Inc. All rights reserved.
ISSN: 00958956
DOI: 10.1016/j.jctb.2019.05.009

Show full item record

Page view(s)

5
Last Week
0
Last month
0
checked on Jun 24, 2024

Google ScholarTM

Check

Altmetric