Toroidal grid minors and stretch in embedded graphs

J 2020

Toroidal grid minors and stretch in embedded graphs

CHIMANI, Markus, Petr HLINĚNÝ a Gelasio SALAZAR

Základní údaje

Originální název

Toroidal grid minors and stretch in embedded graphs

Autoři

CHIMANI, Markus (40 Rakousko), Petr HLINĚNÝ (203 Česká republika, domácí) a Gelasio SALAZAR (484 Mexiko)

Vydání

JOURNAL OF COMBINATORIAL THEORY SERIES B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2020, 0095-8956

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 1.317

Kód RIV

RIV/00216224:14330/20:00114098

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1016/j.jctb.2019.05.009

UT WoS

000503324900011

Klíčová slova anglicky

Graph embeddings; Compact surfaces; Edge-width; Toroidal grid; Crossing number; Stretch

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 16. 4. 2020 08:56, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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.

Návaznosti

GA17-00837S, projekt VaV

Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems

Citovat

CHIMANI, Markus, Petr HLINĚNÝ a Gelasio SALAZAR. Toroidal grid minors and stretch in embedded graphs. JOURNAL OF COMBINATORIAL THEORY SERIES B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2020, roč. 140, č. 1, s. 323-371. ISSN 0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2019.05.009.

@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Ý a 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, roč.~140, č.~1, s.~323-371. ISSN~0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2019.05.009.

Podrobný výpis o publikaci