Toroidal grid minors and stretch in embedded graphs

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou 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.