Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

D 2022

Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

BALABÁN, Jakub, Petr HLINĚNÝ and Jan JEDELSKÝ

Basic information

Original name

Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

Authors

BALABÁN, Jakub (203 Czech Republic, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Jan JEDELSKÝ (203 Czech Republic, belonging to the institution)

Edition

LNCS 13453. Cham, WG 2022: Graph-Theoretic Concepts in Computer Science, p. 43-55, 13 pp. 2022

Publisher

Springer Nature

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

Switzerland

Confidentiality degree

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

Publication form

printed version "print"

References:

URL URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/22:00127036

Organization unit

Faculty of Informatics

ISBN

978-3-031-15913-8

ISSN

DOI

http://dx.doi.org/10.1007/978-3-031-15914-5_4

UT WoS

000866013700004

Keywords in English

twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence

Abstract

V originále

The new graph parameter twin-width, recently introduced by Bonnet et al., allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, such classes (of small twin-width) include proper interval graphs, and (as digraphs) posets of width k. Inspired by an existing generalization of interval graphs into so-called k-thin graphs, we define a new class of proper k-mixed-thin graphs which largely generalizes proper interval graphs. We prove that proper k-mixed-thin graphs have twin-width linear in k, and that a certain subclass of k-mixed-thin graphs is transduction-equivalent to posets of width 𝑘′ such that there is a quadratic relation between k and 𝑘′.

Links

GA20-04567S, research and development project

Name: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Czech Science Foundation

MUNI/A/1145/2021, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Acronym: SV-FI MAV XI.)

Investor: Masaryk University

MUNI/A/1230/2021, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 22 (Acronym: SKOMU)

Investor: Masaryk University

Citovat

BALABÁN, Jakub, Petr HLINĚNÝ and Jan JEDELSKÝ. Twin-Width and Transductions of Proper k-Mixed-Thin Graphs. In Michael A. Bekos and Michael Kaufmann. WG 2022: Graph-Theoretic Concepts in Computer Science. LNCS 13453. Cham: Springer Nature, 2022, p. 43-55. ISBN 978-3-031-15913-8. Available from: https://dx.doi.org/10.1007/978-3-031-15914-5_4.

@inproceedings{2227560,
   author = {Balabán, Jakub and Hliněný, Petr and Jedelský, Jan},
   address = {Cham},
   booktitle = {WG 2022: Graph-Theoretic Concepts in Computer Science},
   doi = {http://dx.doi.org/10.1007/978-3-031-15914-5_4},
   edition = {LNCS 13453},
   editor = {Michael A. Bekos and Michael Kaufmann},
   keywords = {twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-031-15913-8},
   pages = {43-55},
   publisher = {Springer Nature},
   title = {Twin-Width and Transductions of Proper k-Mixed-Thin Graphs},
   url = {https://link.springer.com/chapter/10.1007/978-3-031-15914-5_4},
   year = {2022}
}

TY  - JOUR
ID  - 2227560
AU  - Balabán, Jakub - Hliněný, Petr - Jedelský, Jan
PY  - 2022
TI  - Twin-Width and Transductions of Proper k-Mixed-Thin Graphs
PB  - Springer Nature
CY  - Cham
SN  - 9783031159138
KW  - twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence
UR  - https://link.springer.com/chapter/10.1007/978-3-031-15914-5_4
N2  - The new graph parameter twin-width, recently introduced by Bonnet et al., allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, such classes (of small twin-width) include proper interval graphs, and (as digraphs) posets of width k. Inspired by an existing generalization of interval graphs into so-called k-thin graphs, we define a new class of proper k-mixed-thin graphs which largely generalizes proper interval graphs. We prove that proper k-mixed-thin graphs have twin-width linear in k, and that a certain subclass of k-mixed-thin graphs is transduction-equivalent to posets of width 𝑘′ such that there is a quadratic relation between k and 𝑘′.
ER  -

BALABÁN, Jakub, Petr HLINĚNÝ and Jan JEDELSKÝ. Twin-Width and Transductions of Proper k-Mixed-Thin Graphs. In Michael A. Bekos and Michael Kaufmann. \textit{WG 2022: Graph-Theoretic Concepts in Computer Science}. LNCS 13453. Cham: Springer Nature, 2022, p.~43-55. ISBN~978-3-031-15913-8. Available from: https://dx.doi.org/10.1007/978-3-031-15914-5\_{}4.

Detailed Information on Publication Record