Back to Search
Start Over
Toroidal grid minors and stretch in embedded graphs.
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2020, Vol. 140, p323-371. 49p. - Publication Year :
- 2020
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MATROIDS
*APPROXIMATION algorithms
*MINORS
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 140
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 139748549
- Full Text :
- https://doi.org/10.1016/j.jctb.2019.05.009