Twinwidth II: small classes
Bonnet, Edouard; Geniet, Colin; Thomassé, Stéphan; Watrigant, Rémi (2022), Twinwidth II: small classes, Combinatorial Theory, 2, 2. 10.5070/C62257876
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/2006.09877Date
2022Journal name
Combinatorial TheoryVolume
2Number
2Publisher
eScholarship
Publication identifier
Metadata
Show full item recordAuthor(s)
Bonnet, EdouardLaboratoire de l'Informatique du Parallélisme [LIP]
Geniet, Colin
Laboratoire de l'Informatique du Parallélisme [LIP]
Thomassé, Stéphan
Laboratoire de l'Informatique du Parallélisme [LIP]
Watrigant, Rémi
Laboratoire de l'Informatique du Parallélisme [LIP]
Abstract (EN)
The recently introduced twinwidth of a graph G is the minimum integer d suchthat G has a dcontraction sequence, that is, a sequence of V (G)− 1 iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most d, where a red edge appears between two sets of identified vertices if they are not homogeneous in G (not fully adjacent nor fully nonadjacent). We show that if a graph admits a dcontraction sequence, then it also has a lineararity tree of f(d)contractions, for some function f. Informally if we accept to worsen the twinwidth bound, we can choose the next contraction from a set of (V (G)) pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twinwidth class is small, i.e., has at most n!cn graphs labeled by [n], for some constant c. This unifies and extends the same result for bounded reewidth graphs [Beineke and Pippert, JCT ’69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA ’04], and proper minorfree classes [Norine et al., JCTB ’06]. It implies in turn that boundeddegree graphs, interval graphs, and unit disk graphs have unbounded twinwidth. The second consequence is an O(log n)adjacency labeling scheme for bounded twinwidth graphs, confirming several cases of the implicit graph conjecture.We then explore the small conjecture that, conversely, every small hereditary class has bounded twinwidth. The conjecture passes many tests. Inspired by sorting networks of logarithmic depth, we show that log(log log d) nsubdivisions ofKn (a small class when d is constant) have twinwidth at most d. We obtain a rather sharp converse with a surprisingly direct proof: the logd+1 nsubdivision of Kn has twinwidth at least d. Secondly graphs with bounded stack or queue number (also small classes) have bounded twinwidth. Thesesparse classes are surprisingly rich since they contain certain (small) classes of expanders. Thirdly we show that cubic expanders obtained by iterated random 2lifts from K4 [Bilu and Linial, Combinatorica ’06] also have bounded twinwidth. These graphs are related to socalled separable permutations and also form a small class. We suggest a promising connection between the small conjecture and group theory.Finally we define a robust notion of sparse twinwidth. We show that for a hereditary class C of bounded twinwidth the five following conditions are equivalent: every graph in C (1) has no Kt,t subgraph for some fixed t, (2) has an adjacency matrix without a dbyd division with a 1 entry in each of the d2 cells for some fixed d, (3) has at most linearly many edges, (4) the subgraph closure of C has bounded twinwidth, and (5) C has bounded expansion. We discuss how sparse classes with similar behavior with respect to clique subdivisions compare to bounded sparse twinwidth.Subjects / Keywords
Twinwidth; Small classes; Expanders; Clique subdivisions; SparsityRelated items
Showing items related by title and author.

Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence

Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence

Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence

Bonnet, Edouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2020) Communication / Conférence

Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Article accepté pour publication ou publié