The recently introduced twin-width of a graph G is the minimum integer d such that G has a d-
contraction sequence, that is, a sequence of| V (G)|–1 iterated vertex identifications for which …

We show that planar graphs have bounded queue-number, thus proving a conjecture of
Heath et al.[66] from 1992. The key to the proof is a new structural tool called layered …

Dujmovi\'c, 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 …

Graph product structure theory expresses certain graphs as subgraphs of the strong product
of much simpler graphs. In particular, an elegant formulation for the corresponding structural …

Hadwiger's Conjecture asserts that every K_h-minor-free graph is properly (h-1)-colourable.
We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every K_h …

This paper examines an approach that allows one to build an efficient system for protecting
the information resources of smart power supply networks from cyberattacks based on the …

An efficient implicit representation of an n-vertex graph G in a family F of graphs assigns to
each vertex of G a binary code of length O (log n) so that the adjacency between every pair …

The planar graph product structure theorem of Dujmović et al.[J. ACM, 67 (2020), 22] states
that every planar graph is a subgraph of the strong product of a graph with bounded …

The most basic lower-bound question in randomized communication complexity is: Does a
given problem have constant cost, or non-constant cost? We observe that this question has …

We prove that for every planar graph X of treedepth h, there exists a positive integer c such
that for every X-minor-free graph G, there exists a graph H of treewidth at most f (h) such that …