Toroidal grid minors and stretch in embedded graphs

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

CHIMANI Markus HLINĚNÝ Petr SALAZAR Gelasio

Rok publikování 2020
Druh Článek v odborném periodiku
Časopis / Zdroj JOURNAL OF COMBINATORIAL THEORY SERIES B
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://arxiv.org/abs/1403.1273
Doi http://dx.doi.org/10.1016/j.jctb.2019.05.009
Klíčová slova Graph embeddings; Compact surfaces; Edge-width; Toroidal grid; Crossing number; Stretch
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.