Geodesic
An improved planar graph product structure theorem
Torsten Ueckerdt ; David Wood1 ; Wendy Yi2
1School of Mathematics, Monash University, Melbourne
2Institute of Theoretical Informatics, Karlsruhe Institute of Technology
The electronic journal of combinatorics, Tome 29 (2022) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every planar graph $G$ there is a graph $H$ with treewidth at most 8 and a path $P$ such that $G\subseteq H\boxtimes P$. We improve this result by replacing "treewidth at most 8" by "simple treewidth at most 6".
DOI : 10.37236/10614
Classification : 05C10, 05C76, 05C70, 05C05
Mots-clés : strong product, treewidth, simple treewidth, tree-decomposition, simple tree-decomposition

Torsten Ueckerdt    ; David Wood  1   ; Wendy Yi  2

1 School of Mathematics, Monash University, Melbourne
2 Institute of Theoretical Informatics, Karlsruhe Institute of Technology 
@article{10_37236_10614,
     author = {Torsten Ueckerdt and David Wood and Wendy Yi},
     title = {An improved planar graph product structure theorem},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {2},
     doi = {10.37236/10614},
     zbl = {1527.05046},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10614/}
}
TY  - JOUR
AU  - Torsten Ueckerdt
AU  - David Wood
AU  - Wendy Yi
TI  - An improved planar graph product structure theorem
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10614/
DO  - 10.37236/10614
ID  - 10_37236_10614
ER  - 
%0 Journal Article
%A Torsten Ueckerdt
%A David Wood
%A Wendy Yi
%T An improved planar graph product structure theorem
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10614/
%R 10.37236/10614
%F 10_37236_10614
Torsten Ueckerdt; David Wood; Wendy Yi. An improved planar graph product structure theorem. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/10614

Cité par Sources :