Other formats:
BibTeX
LaTeX
RIS
@article{1646019, author = {Chimani, Markus and Hliněný, Petr and Salazar, Gelasio}, article_location = {SAN DIEGO}, article_number = {1}, doi = {http://dx.doi.org/10.1016/j.jctb.2019.05.009}, keywords = {Graph embeddings; Compact surfaces; Edge-width; Toroidal grid; Crossing number; Stretch}, language = {eng}, issn = {0095-8956}, journal = {JOURNAL OF COMBINATORIAL THEORY SERIES B}, title = {Toroidal grid minors and stretch in embedded graphs}, url = {http://arxiv.org/abs/1403.1273}, volume = {140}, year = {2020} }
TY - JOUR ID - 1646019 AU - Chimani, Markus - Hliněný, Petr - Salazar, Gelasio PY - 2020 TI - Toroidal grid minors and stretch in embedded graphs JF - JOURNAL OF COMBINATORIAL THEORY SERIES B VL - 140 IS - 1 SP - 323-371 EP - 323-371 PB - ACADEMIC PRESS INC ELSEVIER SCIENCE SN - 00958956 KW - Graph embeddings KW - Compact surfaces KW - Edge-width KW - Toroidal grid KW - Crossing number KW - Stretch UR - http://arxiv.org/abs/1403.1273 L2 - http://arxiv.org/abs/1403.1273 N2 - 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. ER -
CHIMANI, Markus, Petr HLINĚNÝ and Gelasio SALAZAR. Toroidal grid minors and stretch in embedded graphs. \textit{JOURNAL OF COMBINATORIAL THEORY SERIES B}. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2020, vol.~140, No~1, p.~323-371. ISSN~0095-8956. Available from: https://dx.doi.org/10.1016/j.jctb.2019.05.009.
|