Hereditary Graph Product Structure and $\cal H$-clique-width

Jan Jedelsk\'y; Petr Hlin\v{e}n\'y

arxiv: 2403.16789 · v7 · submitted 2024-03-25 · 🧮 math.CO · cs.DM

Hereditary Graph Product Structure and cal H-clique-width

Petr Hlin\v{e}n\'y , Jan Jedelsk\'y This is my paper

Pith reviewed 2026-05-24 03:29 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords H-clique-widthgraph product structureplanar graphsinduced subgraphsstrong producttree-widthclique-widthhereditary properties

0 comments

The pith

Every planar graph is an induced subgraph of the strong product of a path and a tree-width-39 graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines H-clique-width for a class H of graphs as the smallest t such that a given graph G is an induced subgraph of the strong product of some member of H and a graph of clique-width t. This creates a hereditary version of product structure by replacing ordinary subgraph containment with induced-subgraph containment. The authors prove that known product theorems, including the planar case, survive this change of relation and keep their original bounds. A sympathetic reader cares because induced subgraphs appear in many algorithmic and structural questions, so a hereditary formulation makes the theorems applicable to a wider range of graph problems.

Core claim

H-clique-width of G with respect to H is the least integer t such that G is isomorphic to an induced subgraph of the strong product of a graph from H and a graph of clique-width t. The definition directly generalises ordinary clique-width. With this tool the authors reformulate the planar graph product structure theorem so that every planar graph is isomorphic to an induced subgraph of the strong product of a path and a graph of tree-width 39, and they obtain analogous hereditary statements for other known product results.

What carries the argument

H-clique-width, the minimum t such that G is an induced subgraph of the strong product of a member of H and a clique-width-t graph; it carries the hereditary product-structure argument.

If this is right

The planar product structure theorem now applies directly to induced subgraphs while retaining the tree-width bound of 39.
H-clique-width supplies a hereditary analogue of product-structure parameters for any fixed class H such as the class of paths.
Other existing graph product structure theorems can be restated in the same induced-subgraph form.
H-clique-width can be compared directly with tree-width, clique-width and related parameters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Classes of bounded H-clique-width may admit new hereditary algorithms that were not available from the non-hereditary versions.
The same technique could be tested on other containment relations or on different graph products.
Tighter bounds on H-clique-width for planar graphs might be obtainable by refining the existing product constructions.

Load-bearing premise

The strong product combined with induced-subgraph containment preserves the numerical bounds of the original product-structure theorems.

What would settle it

A planar graph that cannot be expressed as an induced subgraph of any strong product of a path and a graph of tree-width at most 39.

read the original abstract

We introduce H-clique-width, a new structural measure of graphs that aims to provide a hereditary analogue of the traditional graph product structure. The definition naturally generalises the ordinary clique-width concept. As a result, for a class H of graphs (such as the class of paths), the H-clique-width of a graph G equals the least integer t such that G is isomorphic to an induced subgraph of the strong product of a graph from H and a graph of clique-width t. We study basic properties of H-clique-width and compare it to other established structural parameters of graphs. Notably, we prove that the celebrated Planar graph product structure theorem by Dujmovic et al., and related graph product structure results, can all be formulated with the induced subgraph containment relation. In particular, every planar graph is isomorphic to an induced subgraph of the strong product of a path and a graph of tree-width 39.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines H-clique-width to restate product structure theorems so they apply directly to induced subgraphs, recovering the planar case with tree-width 39.

read the letter

The main takeaway is that this work defines a new graph parameter, H-clique-width, which serves as a hereditary analogue to clique-width in the context of graph product structures. By doing so, it allows the reformulation of existing product structure theorems, such as the one for planar graphs, using induced subgraph containment rather than the standard subgraph relation. Specifically, they recover that every planar graph is an induced subgraph of the strong product of a path and a graph with tree-width at most 39. The paper does well in presenting a natural generalization. The definition ties the parameter directly to the minimum t where the graph embeds as an induced subgraph into a strong product involving a member of H and a low clique-width graph. This setup makes the hereditary property automatic. They also include comparisons to other structural parameters and basic properties of this new measure. On the positive side, the approach builds on solid prior results without introducing new fitting or data issues. The citation to Dujmović et al. is appropriate, and the adaptation claim for the proofs seems grounded in the structure of the original arguments. Where it might be softer is that much of the value rests on whether this new parameter finds applications beyond the reformulation itself. The central claims are essentially definitional once H-clique-width is accepted, and the induced version doesn't change the numerical bounds. If the full proofs of the adaptation are routine, that could limit the depth, but the perspective shift could still be valuable for the field. This paper is for researchers in structural and algorithmic graph theory, particularly those dealing with planar graphs, minor-closed families, or width parameters. A reader interested in hereditary properties or product decompositions would get the most out of it. Overall, it warrants sending to peer review. The ideas are clearly presented and the motivation is sound, so referees can assess the utility and any technical details in the proofs.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces H-clique-width, a new structural parameter relative to a graph class H. It defines the H-clique-width of G as the least t such that G is isomorphic to an induced subgraph of the strong product of a graph from H and a graph of clique-width t; this is shown to generalize ordinary clique-width. The paper studies basic properties of the parameter and its relations to other measures. It then reformulates several existing graph product structure theorems (including the planar theorem of Dujmović et al.) under induced-subgraph containment in the strong product, yielding in particular that every planar graph is an induced subgraph of the strong product of a path and a graph of tree-width 39.

Significance. If the claims hold, the work supplies a hereditary analogue of product structure theorems that preserves the original quantitative bounds. This is useful for classes closed under induced subgraphs. The definition of H-clique-width cleanly captures the induced-product representation, and the explicit reformulation of the planar and related theorems is a direct strengthening of prior results.

minor comments (2)

[Abstract] Abstract: the statement that the planar theorem 'can all be formulated with the induced subgraph containment relation' would benefit from a one-sentence indication of whether the tree-width bound remains exactly 39 or requires adjustment in the induced setting.
The comparison of H-clique-width to other parameters (mentioned in the abstract) would be clearer if the relations were summarized in a small table rather than only in prose.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the recognition of its significance as a hereditary analogue of product structure theorems, and the recommendation for minor revision. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines H-clique-width directly as the least t such that G is an induced subgraph of a strong product H' ⊠ G' with H' in the class H and cw(G')=t. This is an explicit definition, not a derived claim. The central result reformulates the external Dujmović et al. planar product theorem (and analogues) under induced-subgraph containment, asserting that the original proofs adapt; no equations or steps reduce the new bound (tree-width 39) to a fitted parameter or self-citation chain within the paper. No self-definitional loops, fitted-input predictions, or load-bearing self-citations appear. The derivation is self-contained against the cited external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on standard graph-theoretic definitions of strong product, induced subgraphs, clique-width, and tree-width; the new parameter H-clique-width is introduced by definition with no free parameters or invented entities beyond the parameter itself.

axioms (1)

standard math Properties of the strong product of graphs and induced subgraph isomorphism hold as in standard graph theory.
Invoked in the definition of H-clique-width and all product statements.

invented entities (1)

H-clique-width no independent evidence
purpose: New hereditary width parameter generalizing clique-width via product structures.
Defined directly in the paper; no independent evidence outside the definition is provided.

pith-pipeline@v0.9.0 · 5690 in / 1210 out tokens · 33366 ms · 2026-05-24T03:29:11.168044+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Bekos, Giordano Da Lozzo, Petr Hlin e n \' y , and Michael Kaufmann

Michael A. Bekos, Giordano Da Lozzo, Petr Hlin e n \' y , and Michael Kaufmann. Graph product structure for h-framed graphs. In ISAAC , volume 248 of LIPIcs , pages 23:1--23:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022. https://doi.org/10.4230/LIPICS.ISAAC.2022.23 doi:10.4230/LIPICS.ISAAC.2022.23

work page doi:10.4230/lipics.isaac.2022.23 2022
[2]

Shorter labeling schemes for planar graphs

Marthe Bonamy, Cyril Gavoille, and Michal Pilipczuk. Shorter labeling schemes for planar graphs. SIAM J. Discret. Math. , 36(3):2082--2099, 2022. https://doi.org/10.1137/20M1330464 doi:10.1137/20M1330464

work page doi:10.1137/20m1330464 2082
[3]

Twin-width II: small classes

\' E douard Bonnet, Colin Geniet, Eun Jung Kim, St \' e phan Thomass \' e , and R \' e mi Watrigant. Twin-width II: small classes. In SODA , pages 1977--1996. SIAM , 2021. https://doi.org/10.1137/1.9781611976465.118 doi:10.1137/1.9781611976465.118

work page doi:10.1137/1.9781611976465.118 1977
[4]

Twin-width I: tractable FO model checking

\' E douard Bonnet, Eun Jung Kim, St \' e phan Thomass \' e , and R \' e mi Watrigant. Twin-width I: tractable FO model checking. J. ACM , 69(1):3:1--3:46, 2022. https://doi.org/10.1145/3486655 doi:10.1145/3486655

work page doi:10.1145/3486655 2022
[5]

\' E douard Bonnet, O - joung Kwon, and David R. Wood. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond). CoRR , abs/2202.11858, 2022. URL: https://arxiv.org/abs/2202.11858

work page arXiv 2022
[6]

Locally excluding a minor

Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In LICS , pages 270--279. IEEE Computer Society, 2007. https://doi.org/10.1109/LICS.2007.31 doi:10.1109/LICS.2007.31

work page doi:10.1109/lics.2007.31 2007
[7]

Oxley, and Dirk Vertigan

Guoli Ding, Bogdan Oporowski, James G. Oxley, and Dirk Vertigan. Unavoidable minors of large 3-connected binary matroids. J. Comb. Theory, Ser. B , 66(2):334--360, 1996. https://doi.org/10.1006/JCTB.1996.0026 doi:10.1006/JCTB.1996.0026

work page doi:10.1006/jctb.1996.0026 1996
[8]

Seweryn, and David R

Marc Distel, Robert Hickingbotham, Michal T. Seweryn, and David R. Wood. Powers of planar graphs, product structure, and blocking partitions. In EUROCOMB'23: European Conference on Combinatorics, Graph Theory and Applications , pages 355--361. MUNI Press, Masaryk University, 2023. https://doi.org/https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-049 doi:https://...

work page doi:10.5817/cz.muni.eurocomb23-049 2023
[9]

Adjacency labelling for planar graphs (and beyond)

Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwena \" e l Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). J. ACM , 68(6):42:1--42:33, 2021. https://doi.org/10.1145/3477542 doi:10.1145/3477542

work page doi:10.1145/3477542 2021
[10]

Vida Dujmovic, Louis Esperet, Gwena\"el Joret, Bartosz Walczak, and David R. Wood. Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics , 3 2020. https://doi.org/10.19086/aic.12100 doi:10.19086/aic.12100

work page doi:10.19086/aic.12100 2020
[11]

Vida Dujmovic, Gwena \" e l Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. J. ACM , 67(4):22:1--22:38, 2020. https://doi.org/10.1145/3385731 doi:10.1145/3385731

work page doi:10.1145/3385731 2020
[12]

Vida Dujmovic, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. J. Comb. Theory, Ser. B , 162:34--67, 2023. https://doi.org/10.1016/J.JCTB.2023.03.004 doi:10.1016/J.JCTB.2023.03.004

work page doi:10.1016/j.jctb.2023.03.004 2023
[13]

Zdenek Dvo r \' a k, Tony Huynh, Gwena \" e l Joret, Chun - Hung Liu, and David R. Wood. Notes on graph product structure theory. In 2019-20 MATRIX Annals , pages 513--533, Cham, 2021. Springer International Publishing

work page 2019
[14]

Fellows, Frances A

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width is NP -complete. SIAM J. Discret. Math. , 23(2):909--939, 2009. https://doi.org/10.1137/070687256 doi:10.1137/070687256

work page doi:10.1137/070687256 2009
[15]

Deciding first-order properties of locally tree-decomposable structures

Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM , 48(6):1184--1206, 2001. https://doi.org/10.1145/504794.504798 doi:10.1145/504794.504798

work page doi:10.1145/504794.504798 2001
[16]

Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar

Petr Hlin e n \' y and Jan Jedelsk \' y . Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar. In ICALP , volume 261 of LIPIcs , pages 75:1--75:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. https://doi.org/10.4230/LIPICS.ICALP.2023.75 doi:10.4230/LIPICS.ICALP.2023.75

work page doi:10.4230/lipics.icalp.2023.75 2023
[17]

Transductions of graph classes admitting product structure

Petr Hlin e n \' y and Jan Jedelsk \' y . Transductions of graph classes admitting product structure. CoRR , abs/2501.18326, 2025. URL: http://arxiv.org/abs/2501.18326

work page arXiv 2025
[18]

Finding branch-decompositions and rank-decompositions.SIAM Journal on Computing, 38(3):1012–1032, 2008.doi:10.1137/070685920

Petr Hlin e n \' y and Sang - il Oum. Finding branch-decompositions and rank-decompositions. SIAM J. Comput. , 38(3):1012--1032, 2008. https://doi.org/10.1137/070685920 doi:10.1137/070685920

work page doi:10.1137/070685920 2008
[19]

Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs

Hugo Jacob and Marcin Pilipczuk. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. In WG , volume 13453 of Lecture Notes in Computer Science , pages 287--299. Springer, 2022. https://doi.org/10.1007/978-3-031-15914-5\_21 doi:10.1007/978-3-031-15914-5\_21

work page doi:10.1007/978-3-031-15914-5 2022
[20]

Twin-width of graphs on surfaces

Daniel Kr \' a l, Krist \' y na Pek \' a rkov \' a , and Kenny Storgel. Twin-width of graphs on surfaces. In MFCS , volume 306 of LIPIcs , pages 66:1--66:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024. https://doi.org/10.4230/LIPICS.MFCS.2024.66 doi:10.4230/LIPICS.MFCS.2024.66

work page doi:10.4230/lipics.mfcs.2024.66 2024
[21]

Algorithmic meta-theorems for restrictions of treewidth

Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica , 64(1):19--37, 2012. https://doi.org/10.1007/S00453-011-9554-X doi:10.1007/S00453-011-9554-X

work page doi:10.1007/s00453-011-9554-x 2012
[22]

Approximating clique-width and branch-width

Sang - il Oum and Paul Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B , 96(4):514--528, 2006. https://doi.org/10.1016/J.JCTB.2005.10.006 doi:10.1016/J.JCTB.2005.10.006

work page doi:10.1016/j.jctb.2005.10.006 2006
[23]

Wood, and Wendy Yi

Torsten Ueckerdt, David R. Wood, and Wendy Yi. An improved planar graph product structure theorem. Electron. J. Comb. , 29(2), 2022. https://doi.org/10.37236/10614 doi:10.37236/10614

work page doi:10.37236/10614 2022

[1] [1]

Bekos, Giordano Da Lozzo, Petr Hlin e n \' y , and Michael Kaufmann

Michael A. Bekos, Giordano Da Lozzo, Petr Hlin e n \' y , and Michael Kaufmann. Graph product structure for h-framed graphs. In ISAAC , volume 248 of LIPIcs , pages 23:1--23:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022. https://doi.org/10.4230/LIPICS.ISAAC.2022.23 doi:10.4230/LIPICS.ISAAC.2022.23

work page doi:10.4230/lipics.isaac.2022.23 2022

[2] [2]

Shorter labeling schemes for planar graphs

Marthe Bonamy, Cyril Gavoille, and Michal Pilipczuk. Shorter labeling schemes for planar graphs. SIAM J. Discret. Math. , 36(3):2082--2099, 2022. https://doi.org/10.1137/20M1330464 doi:10.1137/20M1330464

work page doi:10.1137/20m1330464 2082

[3] [3]

Twin-width II: small classes

\' E douard Bonnet, Colin Geniet, Eun Jung Kim, St \' e phan Thomass \' e , and R \' e mi Watrigant. Twin-width II: small classes. In SODA , pages 1977--1996. SIAM , 2021. https://doi.org/10.1137/1.9781611976465.118 doi:10.1137/1.9781611976465.118

work page doi:10.1137/1.9781611976465.118 1977

[4] [4]

Twin-width I: tractable FO model checking

\' E douard Bonnet, Eun Jung Kim, St \' e phan Thomass \' e , and R \' e mi Watrigant. Twin-width I: tractable FO model checking. J. ACM , 69(1):3:1--3:46, 2022. https://doi.org/10.1145/3486655 doi:10.1145/3486655

work page doi:10.1145/3486655 2022

[5] [5]

\' E douard Bonnet, O - joung Kwon, and David R. Wood. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond). CoRR , abs/2202.11858, 2022. URL: https://arxiv.org/abs/2202.11858

work page arXiv 2022

[6] [6]

Locally excluding a minor

Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In LICS , pages 270--279. IEEE Computer Society, 2007. https://doi.org/10.1109/LICS.2007.31 doi:10.1109/LICS.2007.31

work page doi:10.1109/lics.2007.31 2007

[7] [7]

Oxley, and Dirk Vertigan

Guoli Ding, Bogdan Oporowski, James G. Oxley, and Dirk Vertigan. Unavoidable minors of large 3-connected binary matroids. J. Comb. Theory, Ser. B , 66(2):334--360, 1996. https://doi.org/10.1006/JCTB.1996.0026 doi:10.1006/JCTB.1996.0026

work page doi:10.1006/jctb.1996.0026 1996

[8] [8]

Seweryn, and David R

Marc Distel, Robert Hickingbotham, Michal T. Seweryn, and David R. Wood. Powers of planar graphs, product structure, and blocking partitions. In EUROCOMB'23: European Conference on Combinatorics, Graph Theory and Applications , pages 355--361. MUNI Press, Masaryk University, 2023. https://doi.org/https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-049 doi:https://...

work page doi:10.5817/cz.muni.eurocomb23-049 2023

[9] [9]

Adjacency labelling for planar graphs (and beyond)

Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwena \" e l Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). J. ACM , 68(6):42:1--42:33, 2021. https://doi.org/10.1145/3477542 doi:10.1145/3477542

work page doi:10.1145/3477542 2021

[10] [10]

Vida Dujmovic, Louis Esperet, Gwena\"el Joret, Bartosz Walczak, and David R. Wood. Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics , 3 2020. https://doi.org/10.19086/aic.12100 doi:10.19086/aic.12100

work page doi:10.19086/aic.12100 2020

[11] [11]

Vida Dujmovic, Gwena \" e l Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. J. ACM , 67(4):22:1--22:38, 2020. https://doi.org/10.1145/3385731 doi:10.1145/3385731

work page doi:10.1145/3385731 2020

[12] [12]

Vida Dujmovic, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. J. Comb. Theory, Ser. B , 162:34--67, 2023. https://doi.org/10.1016/J.JCTB.2023.03.004 doi:10.1016/J.JCTB.2023.03.004

work page doi:10.1016/j.jctb.2023.03.004 2023

[13] [13]

Zdenek Dvo r \' a k, Tony Huynh, Gwena \" e l Joret, Chun - Hung Liu, and David R. Wood. Notes on graph product structure theory. In 2019-20 MATRIX Annals , pages 513--533, Cham, 2021. Springer International Publishing

work page 2019

[14] [14]

Fellows, Frances A

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width is NP -complete. SIAM J. Discret. Math. , 23(2):909--939, 2009. https://doi.org/10.1137/070687256 doi:10.1137/070687256

work page doi:10.1137/070687256 2009

[15] [15]

Deciding first-order properties of locally tree-decomposable structures

Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM , 48(6):1184--1206, 2001. https://doi.org/10.1145/504794.504798 doi:10.1145/504794.504798

work page doi:10.1145/504794.504798 2001

[16] [16]

Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar

Petr Hlin e n \' y and Jan Jedelsk \' y . Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar. In ICALP , volume 261 of LIPIcs , pages 75:1--75:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. https://doi.org/10.4230/LIPICS.ICALP.2023.75 doi:10.4230/LIPICS.ICALP.2023.75

work page doi:10.4230/lipics.icalp.2023.75 2023

[17] [17]

Transductions of graph classes admitting product structure

Petr Hlin e n \' y and Jan Jedelsk \' y . Transductions of graph classes admitting product structure. CoRR , abs/2501.18326, 2025. URL: http://arxiv.org/abs/2501.18326

work page arXiv 2025

[18] [18]

Finding branch-decompositions and rank-decompositions.SIAM Journal on Computing, 38(3):1012–1032, 2008.doi:10.1137/070685920

Petr Hlin e n \' y and Sang - il Oum. Finding branch-decompositions and rank-decompositions. SIAM J. Comput. , 38(3):1012--1032, 2008. https://doi.org/10.1137/070685920 doi:10.1137/070685920

work page doi:10.1137/070685920 2008

[19] [19]

Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs

Hugo Jacob and Marcin Pilipczuk. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. In WG , volume 13453 of Lecture Notes in Computer Science , pages 287--299. Springer, 2022. https://doi.org/10.1007/978-3-031-15914-5\_21 doi:10.1007/978-3-031-15914-5\_21

work page doi:10.1007/978-3-031-15914-5 2022

[20] [20]

Twin-width of graphs on surfaces

Daniel Kr \' a l, Krist \' y na Pek \' a rkov \' a , and Kenny Storgel. Twin-width of graphs on surfaces. In MFCS , volume 306 of LIPIcs , pages 66:1--66:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024. https://doi.org/10.4230/LIPICS.MFCS.2024.66 doi:10.4230/LIPICS.MFCS.2024.66

work page doi:10.4230/lipics.mfcs.2024.66 2024

[21] [21]

Algorithmic meta-theorems for restrictions of treewidth

Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica , 64(1):19--37, 2012. https://doi.org/10.1007/S00453-011-9554-X doi:10.1007/S00453-011-9554-X

work page doi:10.1007/s00453-011-9554-x 2012

[22] [22]

Approximating clique-width and branch-width

Sang - il Oum and Paul Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B , 96(4):514--528, 2006. https://doi.org/10.1016/J.JCTB.2005.10.006 doi:10.1016/J.JCTB.2005.10.006

work page doi:10.1016/j.jctb.2005.10.006 2006

[23] [23]

Wood, and Wendy Yi

Torsten Ueckerdt, David R. Wood, and Wendy Yi. An improved planar graph product structure theorem. Electron. J. Comb. , 29(2), 2022. https://doi.org/10.37236/10614 doi:10.37236/10614

work page doi:10.37236/10614 2022