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.
|
