-
H-Clique-Width and a Hereditary Analogue of Product Structure
Authors:
Petr Hliněný,
Jan Jedelský
Abstract:
We introduce a novel generalization of the notion of clique-width which aims to bridge the gap between classical hereditary width measures and the recently introduced graph product structure theory. Bounding the new H-clique-width, in the special case of H being the class of paths, is equivalent to admitting a hereditary (i.e., induced) product structure of a path times a graph of bounded clique-w…
▽ More
We introduce a novel generalization of the notion of clique-width which aims to bridge the gap between classical hereditary width measures and the recently introduced graph product structure theory. Bounding the new H-clique-width, in the special case of H being the class of paths, is equivalent to admitting a hereditary (i.e., induced) product structure of a path times a graph of bounded clique-width. Furthermore, every graph admitting the usual (non-induced) product structure of a path times a graph of bounded tree-width, has bounded H-clique-width and, as a consequence, it admits the usual product structure in an induced way. We prove further basic properties of H-clique-width in general.
△ Less
Submitted 28 June, 2024; v1 submitted 25 March, 2024;
originally announced March 2024.
-
Twin-width of Planar Graphs is at most 8, and some Related Bounds
Authors:
Petr Hliněný,
Jan Jedelský
Abstract:
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020], and has interesting applications in the areas of logic on graphs and in parameterized algorithmics. Very briefly, the essence of twin-width is in a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of th…
▽ More
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020], and has interesting applications in the areas of logic on graphs and in parameterized algorithmics. Very briefly, the essence of twin-width is in a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. While for many natural graph classes it is known that their twin-width is bounded, published upper bounds on the twin-width in non-trivial cases are very often "astronomically large".
We focus on planar graphs, which are known to have bounded twin-width already since the introduction of it, but it took some time for the first explicit "non-astronomical" upper bounds to come. Namely, in the order of preprint appearance, it was the bound of at most 183 by Jacob and Pilipczuk [arXiv, January 2022], and 583 by Bonnet, Kwon and Wood [arXiv, February 2022]. Subsequent arXiv manuscripts in 2022 improved the bound down to 37 (Bekos et al.), 11 and 9 (both by Hliněný). We further elaborate on the approach used in the latter manuscripts, proving that the twin-width of every planar graph is at most 8, and construct a witnessing contraction sequence in linear time. Note that the currently best lower-bound planar example is of twin-width 7, by Král and Lamaison [arXiv, September 2022]. We also prove small explicit upper bounds on the twin-width of bipartite planar and 1-planar graphs (6 and 16), and of map graphs (38). The common denominator of all these results is the use of a novel specially crafted recursive decomposition of planar graphs, which may be found useful also in other areas.
△ Less
Submitted 7 December, 2023; v1 submitted 16 October, 2022;
originally announced October 2022.
-
Twin-width and Transductions of Proper k-Mixed-Thin Graphs
Authors:
Jakub Balabán,
Petr Hliněný,
Jan Jedelský
Abstract:
The new graph parameter twin-width, introduced by Bonnet, Kim, Thomass e and Watrigant in 2020, 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, classes of efficiently bounded twin-width include proper interval graphs, and (as digraphs) posets of width k. Inspired…
▽ More
The new graph parameter twin-width, introduced by Bonnet, Kim, Thomass e and Watrigant in 2020, 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, classes of efficiently bounded 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 slight subclass of k-mixed-thin graphs is transduction-equivalent to posets of width k' such that there is a quadratic-polynomial relation between k and k'. In addition to that, we also give an abstract overview of the so-called red potential method which we use to prove our twin-width bounds.
△ Less
Submitted 6 November, 2022; v1 submitted 25 February, 2022;
originally announced February 2022.
