refkeygray.85 labelkeygray.85

# NOTES ON A PATH TO AI ASSISTANCE IN MATHEMATICAL REASONING

Alex Kontorovich<EMAIL_ADDRESS>Department of Mathematics,
Rutgers University, New Brunswick, NJ

Kontorovich is partially supported by NSF grant DMS-1802119 and BSF grant
2020119.

These informal notes are based on the author’s lecture at the National
Academies of Science, Engineering, and Mathematics workshop on “AI to Assist
Mathematical Reasoning” in June 2023. The goal is to think through a path by
which we might arrive at AI that is useful for the research mathematician.

##  1\. Finding a Holy Grail

I find utility in trying to work backwards: What could be our end goal in this
game, our “Holy Grail”? One possibility is the following.

######  Holy Grail 1.

AI solves the Riemann hypothesis.

Of course this applies more generally to any major, longstanding problem of
interest to mathematicians. I see two ways this could go:

  1. (1)

AI might give a million-line, dense, incomprehensible proof of RH. In this
nightmare scenario, people like me will spend the rest of their lives just
trying to understand what it’s saying and why.111Perhaps (1) is anyway
unreasonable, as some other AI will digest the proof and explain it to us in
terms we understand?

  2. (2)

Alternatively, AI might give a perfectly comprehensible, beautiful proof of
RH! (Is this a dream? Or also a nightmare?! Now I’m really out of business,
and spending my life prompting GPT instead of relishing the thought of solving
a hard problem.)

Another potential target, instead of solving our problems, may be the
following.

######  Holy Grail 2.

AI starts making its own beautiful definitions, conjectures, and theorems,
doing “Alien math” way ahead of what humans can comprehend and utilize.

The history of mathematics is full of vignettes, such as Monstrous Moonshine,
or the Dyson-Montgomery tea conversation, in which patterns across seemingly
unrelated fields were serendipitously discovered and exploited to uncover
(perhaps still conjectural) underlying structures. Humans already do this on
their own, though such discoveries are relatively few and far between. AI has
also already proved somewhat effective here; see, e.g., [DVB+21], and the more
recent discovery [HLOP22] of murmurations in the Fourier coefficients of
elliptic curves. (That said, in these examples, “AI” really refers to:
statistical inference analysis on large datasets produced via human-written
deterministic algorithms. In this sense, it is not all that different from
Gauss conjecturing the Prime Number Theorem from large tables of primes.) Can
AI discover structures such as perfectoid spaces or infinity categories? If
so, might it find novel structures, definitions, conjectures, and theorems,
with sufficient rapidity that human beings have no hope of keeping up?

As far as I can tell, both of these Holy Grails are distant science fiction.
Here is a more modest, medium-term possibility.

######  Holy Grail 3.

AI can _assist_ mathematicians in theorem proving.

Certainly if AI can’t even do that, then there’s no hope of the more ambitious
Holy Grails. What might we consider “success” here?

The current workflow of a research mathematician typically involves something
like:

  * •

Formulating an idea for a major theorem or a class of theorems.

  * •

Trying to break up these theorems into smaller propositions.

  * •

Deriving each proposition from a set of even smaller lemmas.

  * •

At each scale (lemma/proposition/theorem), employing standard techniques or
exploring new, non-standard approaches, perhaps doing literature searches or
looking for analogous arguments that have appeared in other settings.222LLMs
like ChatGPT are already capable of sometimes giving helpful pointers, but
this mostly happens when humans have already found connections and written
about them.

  * •

Iterating through the whole process, modifying the statements, refining
approaches, and discovering alternative techniques, etc etc, all hoping for
eventual success.

A lot of this does feel like it could be outsourced. In other sciences, PIs
have labs of PhD students and postdocs who fight the various local battles in
parallel, with the PI serving as a General overseeing the action and making
“global” adjustments to the plan of attack. For many reasons, we don’t/can’t
do this in math. But could AI help automate some of these steps, perhaps
drastically speeding up the workflow of a mathematician capable of harnessing
these tools?

Let’s continue working backwards from Holy Grail 3 as our target.

##  2\. Necessity of Interactive Theorem Provers

As experience shows, for “AI” to do anything, it first needs to be trained on
extremely large data sets. A first question might be: data sets of what
exactly?

######  Conjecture 1.

Large language models (LLMs) trained on natural language alone will _not_
reason reliably at the level of professional mathematics.

Mathematics is communicated in such a way as to appear to be a language
amenable to sampling. But at its core, the underlying arguments are always
deterministic: either logically sound or not. Language itself exhibits
stochastic properties, with various ways to express ideas and infer meaning.
Mathematics, on the other hand, relies on an underlying language, such as
English, but its essence is entirely deterministic and precise.

For instance, if an LLM generates a 98% believable Bach chorale, we would be
delighted. However, if it produces a 98% correct mathematical argument, it may
be completely worthless. That missing 2% might be a reduction to a problem as
difficult as the original, or it may just be flat out wrong. The processes of
“production” and “editing” are distinct functions, even within the human
brain. LLMs excel at stochastic generation, producing the next word (or token)
by sampling from a statistical distribution, whereas mathematics demands
deterministic editing. That is my perspective, for what it’s worth.

Counterpoint: OpenAI, Google, and many other groups much smarter than me and
with many more resources than I have are actively working to disprove
Conjecture 1! They believe that, if only LLMs were given enough training data,
enough parameters, enough transformers, etc, then they would solve
professional-level mathematical problems, as they’ve already succeeded
handsomely with a variety of standardized math and reasoning tests. (Their
work in this direction is not unrelated to issues of “alignment”, which we
have neither the time nor expertise to delve into here…)

And even if I’m completely wrong, and LLMs are indeed capable of producing, in
natural language, something that reads like a perfect math paper, how can we
ever trust it? We would be burdened with the responsibility of refereeing the
thousands or millions of papers they generate to discern the correct ones from
mere “hallucinations”.

######  Conjecture 2.

The path to AI assisting research mathematicians is through an adversarial
process, likely involving Interactive Theorem Provers (e.g., Lean, Isabelle,
Coq, etc).

##  3\. A refined Holy Grail

Here is a suggested mechanism to aim for Holy Grail 3. Imagine the following
scenario.

######  Holy Grail 4.

One asks a ChatGPT-like prompt in natural language about a Lemma or technique
idea. The LLM bounces back and forth with Lean,333Here and throughout, we will
use “Lean” as a shorthand for any Interactive Theorem Prover, perhaps even one
not yet invented. and eventually outputs in natural language: “here is what
I’m able to prove about your question”, together with a formalized certificate
that the argument described is valid.

This possibility seems, to me, much less out of reach, at least in the medium-
term. If one accepts this as a desired goal, the question again becomes: how
do we train AI for this task? Any of the GPT4, Bard, or other such systems, to
work nearly as well as they do, typically require training on trillions of
data points, whether these are measured in bytes, lines of text, tokens, etc.
In contrast, if we consider the current formalized libraries of mathematics,
we might have on the order of 10 million “data points”, again, whether that
means: raw bytes, lines of code, pairs of goal states and next proof lines, or
pairs of natural language lines and formal lines, or something else entirely.

This naturally leads to the following:

######  Conjecture 3.

The current rate-limiting step for AI proof assistance is: producing orders of
magnitude more lines of formalized professional-level mathematics.

If you believe this conjecture, then the next natural question is: how to
produce lots more?

##  4\. Paths to Large Datasets of Formalized Mathematics

Producing high-quality formalized mathematics is difficult! Modern mathematics
requires interactions of many different fields in concert. One needs huge
libraries that can all interact with one another compatibly (this is one of
the main features of Lean’s “mathlib” library). I see (at least) three reasons
to be somewhat optimistic here.

Figure 1. A formal proof from [KM22]

  1. (1)

The pace of production has been steadily increasing. Three vignettes to
illustrate this are:

    1. (a)

It took two years from Ellenberg-Gijswijt’s 2017 solution [EG17] of the Cap
Set Conjecture to its 2019 formalization [DHL19].

    2. (b)

It took one year from Gardam’s 2021 counterexample [Gar21] to Kaplansky’s unit
conjecture for group rings to its 2022 formalization [GT22].

    3. (c)

The formalization [BM22] of Bloom’s solution [Blo21] to the Edros-Graham
density conjecture on Egyptian unit fractions arrived before its referee
reports!

(Of course these results are cherry-picked, and it is still relatively
difficult to formalize most research-level mathematics…)

  2. (2)

The levels of complexity that Theorem Proving software can handle is
advancing. We’ve gone from:

    1. (a)

Proving difficult statements about simple objects, such the formalization
[Avi04] of the Prime Number Theorem: the primes are elementary to define, but
the statement on their asymptotic behavior is relatively non-trivial to
establish.

    2. (b)

Proving elementary statements about complicated objects, such as the
formalization [BCM20] of the mere definition of perfectoid spaces.

    3. (c)

Proving difficult statements about complicated objects, such as the success of
the Liquid Tensor Experiment [Sch22, Cm22].

  3. (3)

With enough progress on Application Programming Interface (API), formalized
proofs can (sometimes) be made to work almost exactly how human ones do. One
example of this is the formalization [KM22] of the author and Heather Macbeth
of the fact that the quotient $X/\Gamma$ of a locally compact Hausdorff space
$X$ by a discontinuous group action $\Gamma$ is itself Hausdorff. This
statement is certainly nothing earthshattering; it’s the kind of thing a 1st
year PhD student (or advanced undergrad) should be able to solve, but it’s
also not entirely trivial. What’s more remarkable, to me at least, is that the
proof, shown in Figure 1, reads almost verbatim like a human one, with nearly
each line of the formalization having a corresponding line in a natural
language argument. (Of course one needs to first become familiar with the
syntax of Lean, in the same way that one eventually becomes accustomed to
reading dollar signs and backslashes in LaTeX and visualizing the outcome of
compilation…)

Here is a big reason to be pessimistic.

######  Theorem 4.

All that said, humans alone will _never_ reach a trillion lines of formalized
mathematics.

The proof is obvious. Equally obvious, then, is that humans need automated
assistance in formalization! This idea is far from original, and was proposed
already by Szegedy in 2020 [Sze20]. Before AI can assist mathematicians with
solving new problems, it had better get really good at formalizing known (to
humans) solutions! There are many groups already working hard on this from a
wide variety of viewpoints, see, e.g., [RLBS20, WJL+22, LLL+22, JWZ+22] for
but a sample. Many more are needed, in this author’s opinion.444Added in
print: the authors of [GZA+23] are able to achieve impressive results in the
restricted realm of coding, training on “only” billions of tokens, rather than
trillions. That said, the path to the former may not be so different from the
latter; that is, a mechanism to reach a billion, say, lines of formalized
mathematics, seems likely to also reach a trillion.

In closing, it seems prudent to direct resources towards developing a positive
feedback loop between human and AI formalization, with progress in each
driving the other. This can hopefully eventually build up enough of a training
database from which other AI systems can effectively learn, and become truly
useful and reliable as research assistants. Who knows where things will go
from there.

Acknowledgements: The author would like to thank Kevin Buzzard, Drew
Sutherland, and Geordie Williamson for many comments and suggestions that
improved on an earlier draft.

## References

  * [Avi04] Jeremy Avigad.  Notes on a formalization of the prime number theorem, 2004.  https://www.andrew.cmu.edu/user/avigad/Papers/pntnotes.pdf.
  * [BCM20] K. Buzzard, J. Commelin, and P. Massot.  Formalising perfectoid spaces.  POPL: Principles of Programming Languages, Association for Computing Machinery, pages 299–312, 2020.
  * [Blo21] Thomas Bloom.  On a density conjecture about unit fractions, 2021.  https://arxiv.org/abs/2112.03726.
  * [BM22] Thomas Bloom and Bhavik Mehta.  Unit fractions, 2022.  https://b-mehta.github.io/unit-fractions/.
  * [Cm22] Johan Commelin and mathlib.  Completion of the liquid tensor experiment, 2022.  https://leanprover-community.github.io/blog/posts/lte-final/.
  * [DHL19] Sander R. Dahmen, Johannes Hölzl, and Robert Y. Lewis.  Formalizing the solution to the cap set problem.  In 10th International Conference on Interactive Theorem Proving, volume 141 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 15, 19. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.
  * [DVB+21] Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, Daniel Zheng, Nenad Tomašev, Richard Tanburn, Peter Battaglia, Charles Blundell, András Juhász, Marc Lackenby, Geordie Williamson, Demis Hassabis, and Pushmeet Kohli.  Advancing mathematics by guiding human intuition with AI.  Nature, 600:70–74, 2021.
  * [EG17] Jordan S. Ellenberg and Dion Gijswijt.  On large subsets of $\mathbb{F}^{n}_{q}$ with no three-term arithmetic progression.  Ann. of Math. (2), 185(1):339–343, 2017.
  * [Gar21] Giles Gardam.  A counterexample to the unit conjecture for group rings.  Ann. of Math. (2), 194(3):967–979, 2021.
  * [GT22] Siddhartha Gadgil and Anand Rao Tadipatri.  Formalizing Gardam’s disproof of Kaplansky’s unit conjecture, 2022\.  https://siddhartha-gadgil.github.io/automating-mathematics/posts/formalizing-gardam-disproof-kaplansky-conjecture/.
  * [GZA+23] Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, Adil Salim, Shital Shah, Harkirat Singh Behl, Xin Wang, Sébastien Bubeck, Ronen Eldan, Adam Tauman Kalai, Yin Tat Lee, and Yuanzhi Li.  Textbooks are all you need, 2023.  https://arxiv.org/abs/2306.11644.
  * [HLOP22] Yang-Hui He, Kyu-Hwan Lee, Thomas Oliver, and Alexey Pozdnyakov.  Murmurations of elliptic curves, 2022.  https://arxiv.org/abs/2204.10140.
  * [JWZ+22] Albert Q. Jiang, Sean Welleck, Jin Peng Zhou, Wenda Li, Jiacheng Liu, Mateja Jamnik, Timothée Lacroix, Yuhuai Wu, and Guillaume Lample.  Draft, sketch, and prove: Guiding formal theorem provers with informal proofs, 2022.  https://arxiv.org/abs/2210.12283.
  * [KM22] Alex Kontorovich and Heather Macbeth.  “const_mul_action” in Lean3’s mathlib, 2022.  https://github.com/leanprover-community/mathlib/blob/f23a09ce6d3f367220dc3cecad6b7eb69eb01690/src/topology/algebra/const_mul_action.lean.
  * [LLL+22] Guillaume Lample, Marie-Anne Lachaux, Thibaut Lavril, Xavier Martinet, Amaury Hayat, Gabriel Ebner, Aurélien Rodriguez, and Timothée Lacroix.  Hypertree proof search for neural theorem proving, 2022.  https://arxiv.org/abs/2205.11491.
  * [RLBS20] Markus N. Rabe, Dennis Lee, Kshitij Bansal, and Christian Szegedy.  Mathematical reasoning via self-supervised skip-tree training, 2020.  https://arxiv.org/abs/2006.04757.
  * [Sch22] Peter Scholze.  Liquid tensor experiment.  Exp. Math., 31(2):349–354, 2022.
  * [Sze20] Christian Szegedy, editor.  A Promising Path Towards Autoformalization and General Artificial Intelligence, 2020.
  * [WJL+22] Yuhuai Wu, Albert Q. Jiang, Wenda Li, Markus N. Rabe, Charles Staats, Mateja Jamnik, and Christian Szegedy.  Autoformalization with large language models, 2022.  https://arxiv.org/abs/2205.12615.


+1 (716) 645-1468 University at Buffalo] Department of Mechanical and
Aerospace Engineering, University at Buffalo

# Effect of structure-based training on 3D localization precision and quality

Armin Abdehkahka  Craig Snoeyink<EMAIL_ADDRESS>[

###### Abstract

This study introduces a structural-based training approach for CNN-based
algorithms in single-molecule localization microscopy (SMLM) and 3D object
reconstruction. We compare this approach with the traditional random-based
training method, utilizing the LUENN package as our AI pipeline. The
quantitative evaluation demonstrates significant improvements in detection
rate and localization precision with the structural-based training approach,
particularly in varying signal-to-noise ratios (SNRs). Moreover, the method
effectively removes checkerboard artifacts, ensuring more accurate 3D
reconstructions. Our findings highlight the potential of the structural-based
training approach to advance super-resolution microscopy and deepen our
understanding of complex biological systems at the nanoscale.

Keywords: Super-resolution Microscopy, structure-based training, Deep
Convolutional Neural Network, Localization, 3D Reconstruction

##  1 Introduction

Single Molecule Localization Microscopy (SMLM) is a revolutionary technique in
Super-resolution Microscopy that surpasses the diffraction limit, providing
enhanced imaging resolution 1. This breakthrough allows researchers to study
cellular functions relevant to both health and disease with unprecedented
detail. Among various super-resolution imaging techniques, SMLM stands out by
offering the highest achievable resolution, ranging from 20 to 30 nm, using
relatively simple experimental equipment 2.

Despite its exceptional resolution, SMLM comes with challenges in terms of
data analysis and imaging speed compared to other super-resolution techniques
like STED microscopy 3, SIM 4, and NSOM 5. SMLM data analysis is complex and
time-consuming, and the imaging speed is relatively slower, requiring several
minutes to capture a complete dataset.

In SMLM, localization precision, and data interpretation heavily rely on the
sparsity of fluorophores, ensuring well-separated point spread functions
(PSFs). Achieving this requires time-separating frames and activating
individual fluorophores. While increasing the fluorophore density per frame
can enhance acquisition speed, it also introduces limitations. Higher
fluorophore density can lead to PSF overlap, resulting in reduced detection
accuracy and localization precision 6. Additionally, high-density frames may
produce artifacts like false structures, artificial sharpening, and
checkerboard artifacts 7, 6.

Given the demand for fast and accurate analysis methods that eliminate
artifacts, especially in high-density frames, the development of an improved
algorithm is highly sought after 7. This advancement would enable precise
localization in ultra-high densities, facilitating more accurate
quantification and analysis of dynamic events, such as protein interactions in
membrane fluidity analysis 8 within sub-cellular structures. Moreover, this
progress in SMLM technology would have broad applications, including drug
discovery, where a deeper understanding of protein interactions is essential
for designing effective therapies.

Traditional mathematical-based localization algorithms, such as Maximum
Likelihood Estimation (MLE) 9 and non-linear least squares (LS) 10, treat each
point spread function (PSF) independently without considering their
surroundings. While effective for sparse emitters with non-overlapping PSFs,
these methods suffer from reduced precision when PSFs overlap, as they are
unable to extract patterns from overlapping PSFs and leverage combined
information for improved accuracy.

Recent advances in SMLM have seen significant progress in addressing these
limitations by utilizing Convolutional Neural Networks (CNNs). State-of-the-
art CNN-based algorithms, such as DeepLoco 11, DeepSTORM3D 12, DECODE 6, and
LUENN 13, have achieved remarkable improvements in analysis times and
localization accuracy. These deep-learning approaches excel at handling large
numbers of emitters without a significant increase in computational time.
However, highly overlapped patterns still pose challenges and can compromise
reconstruction quality in scenarios with dense emitter distributions.

The performance of a CNN-based localization algorithm is heavily reliant on
the training method used. While supervised learning is a common approach for
robust training, it necessitates a large training dataset to avoid
overfitting. However, in SMLM, obtaining real experimental frames with
corresponding ground-truth data is limited, posing a challenge for training.
To address this challenge, researchers often employ a reasonable frame
generative model capable of reproducing data as closely as possible to real
frames 11, 12, 6. The success of the AI model greatly depends on the accuracy
of this generative model, and any mismatch between the simulated and
experimental data could lead to reduced performance.

Frame simulation is a crucial three-step process in training a model for SMLM
and 3D reconstruction of biological samples. Firstly, candidate seeds are
randomly activated in a 3D grid domain, and their locations are selected
within a confined domain both laterally (within the frame size) and axially
(within the depth range). Next, the generative model employs the Point Spread
Function (PSF) model to fill the frame with PSF distributions. Finally, camera
noise is applied to simulate realistic frames that closely resemble
experimental data.

While recent works on generative models have performed satisfactorily in PSF
engineering modeling and camera noise estimation, less attention has been
given to the sampling methods. Improving the sampling methods in frame
simulation is an area of potential advancement to enhance the overall
performance and accuracy of CNN-based localization algorithms in SMLM. In the
context of seed sampling for frame simulation, the traditional approach
adopted by researchers is the Complete Spatial Randomness (CSR) hypothesis.
This method assumes that the points in the dataset are distributed randomly
and independently throughout the study area, without any specific spatial
patterns or interactions. Essentially, the points follow a homogeneous Poisson
process, where the probability of finding a point at any location within the
study area remains uniform and is not influenced by the presence or absence of
other points.

The sampling method based on the CSR hypothesis is widely used as a baseline
reference for evaluating deviations from randomness and uncovering any
underlying spatial structures or dependencies present in real-world point
datasets. By comparing the performance of other sampling methods to CSR,
researchers can assess the effectiveness and efficiency of their frame
simulation approaches in accurately representing and reproducing experimental
data.

In the context of Single-Molecule Localization Microscopy (SMLM) and 3D
reconstruction, the primary objective is to achieve rapid and accurate
reconstruction of 3D objects. Given the specific goal of accurate 3D
reconstruction, the CSR method, which assumes random and independent
distributions, does not capture the intricacies and spatial relationships
present in real 3D structures. Instead, specialized sampling methods that
consider the actual 3D structure and interactions between points are necessary
to produce realistic frame simulations. This is because SMLM datasets consist
of collections of 3D points that are correlated in location due to the surface
or geometry of an object or environment.

In our research, we propose a structure-based training approach to enhance the
performance of CNN-based algorithms, especially in ultra-high emitter
densities. Structure-based training involves considering the underlying
structure and relationships between neighboring PSFs, instead of treating data
as independent samples. By leveraging the contextual information and
correlations between data points, the algorithm can make more informed
predictions and capture dependencies present in the structured data. Sampling
from cloud points, where overlapping patterns have meaningful relationships,
allows the CNN to reconstruct a more accurate 3D view of the structure.

Incorporating structure-based training can provide several advantages,
including improved accuracy, robustness, and generalization performance of the
trained model. By advancing the localization precision of CNN-based algorithms
in SMLM, we can unlock the full potential of SMLM and enhance our
understanding of molecular interactions in biological systems. This research
has the potential to significantly impact the field of super-resolution
microscopy and contribute to breakthroughs in various biological and medical
research areas.

##  2 Methods

In our study, we aimed to compare the effects of two different seed sampling
methods on the performance of a CNN-based localization algorithm. To conduct
the experiments, we utilized the LUENN package, which served as our AI
pipeline, guiding us through each step of the process, including emitters
sampling, frame simulation, model selection, model training, and performance
evaluation. The overall process is illustrated in Figure1.

Figure 1: Comparison Workflow. Contrasting two training methodologies rooted
in random emitter sampling (Approach 1) and structure-based sampling (Approach
2). In both approaches, the LUENN pipeline is employed for frame simulation,
incorporating Astigmatism modality, model training, and evaluation, with
calculations performed for Jaccardian Index and precision assessments.

We utilized the Astigmatism modality in both approaches and trained the model
on three distinct background-to-noise ratios: high, medium, and low. These
three refer to mean photon counts of 1000, 5000, and 20,000 with background
levels of 10, 50, and 200 photons per pixel, respectively. The frame
generative model used in LUENN was based on the method presented by 6, and the
training procedure was comprehensively explained in our previous work 13.

The primary focus of our investigation was to compare two different approaches
in the emitters sampling step. In the first approach, we trained LUENN by
sampling emitters based on the Complete Spatial Randomness (CSR) hypothesis.
In the second approach, emitters were sampled from randomly generated point
clouds, which aim to represent real 3D structures.

After completing the full training of both models, we proceeded to compare
their reconstruction and localization performance using artificially generated
framesets of Microtubules, utilizing the ground-truth data from the MT0
datasets provided by the SMLM Challenge 2016. The ground-truth emitters data
can be accessed through the following LINK. However, it’s worth noting that
the challenge only provided framesets for two specific frame densities,
limiting our comparison’s scope.

To overcome this limitation, we generated an additional nine sets of frames
with varying nominal densities, ranging from 0.38 to 13.0 emitters per frame.
It’s important to mention that these densities are not the actual density that
is formulated as the number of emitters per unit area in the frame. In the
frames where the points’ distribution follows a specific structure, such as a
line or a surface, the actual density may not accurately reflect the
difficulty of localization.

We employed Ripley’s method 14 to calculate the average minimum distance
between the emitters on the simulated frames to address this. Using cross-
correlation, we then identified the frame density with a similar average
minimum distance, in which the seeds were uniformly distributed. This
corresponding frame density was considered the “nominal density” of the frame,
providing a more accurate and broadly applicable quantification metric.

Both models followed the same on-the-fly training procedure, where training
frames were generated randomly during the training process. For training LUENN
with the CSR method, the seeds were randomly sampled across the entire 3D
domain without any constraints. On the other hand, for the structure-based
training, we created three-helix microtubules that spanned the 3D domain, each
containing 5000 seeds. From these sampled point clouds, we selected candidate
emitters, considering the challenges posed by overlapping PSFs along a spiral
curve. It’s important to note that the sampled microtubules were only used for
one frame of the training data and the microtubule structures were
continuously changed throughout the training process.

In Figure 2, we provide two examples of training frames along with their
corresponding labeled frames. These examples showcase the effectiveness of the
structure-based training approach in addressing the challenges of emitter
localization, particularly in cases with overlapping PSFs, thus contributing
to the improved performance of the CNN-based localization algorithm.

Figure 2: Investigating two sampling approaches on the performance of the
LUENN on 3D reconstruction. Approach 1: sampling emitters randomly without
prior information of the real object. Approach 2: Cloud point sampling to give
the model rationale behind the overlapping PSFs. both approaches share the
same method for frame simulation, model training, and performance evaluation
that all are part of the LUENN pipeline.

##  3 Results and discussion

For the quantitative evaluation, we employed two metrics, namely the
Jaccardian index (JI) and the root-mean-square error (RMSE), to assess the
detection rate and localization accuracy in the X, Y, and Z directions in
reconstructing the MT0 dataset. Figure 3a to c presents the Jaccardian index
and volumetric RMSE plotted against the frame densities. The results
demonstrate a significant improvement in both detection rate and localization
precision when using the structural-based training approach. In high signal-
to-noise ratio (SNR) conditions, the structural-based model exhibited an
average of 20% improvement in the detection rate and 35% improvement in RMSE
compared to the traditional random-based training model.

Similar improvements are observed in medium and low SNR scenarios, as shown in
Figures 3b and 3c. In these cases, the structural-based trained model
outperformed the random-based trained model with 7.2% and 2.2% higher
detection rates, respectively. Additionally, on average, the volumetric RMSE
was 28.3 nm and 30.7 nm lower in the structural-based training approach for
medium and low SNRs, respectively. These results demonstrate the robustness
and superior performance of the structural-based training approach in various
SNR conditions, making it a promising method for enhancing the accuracy and
precision of single-molecule localization microscopy (SMLM) in 3D object
reconstruction.

Figures 3d to f present the lateral and axial localization RMSE for high,
medium, and low SNRs, respectively. These results underscore the substantial
improvement in localization precision, particularly in the depth (Z)
direction, further validating the robustness of the structural-based training
approach in achieving accurate 3D object reconstruction, which is the primary
goal of SMLM. An interesting trend in the results is that as the nominal
density increases, our new training method exhibits even better results, as
indicated by the increasing difference between the plots for both lateral and
axial localization RMSE. This finding highlights the effectiveness of the
structural-based training approach in handling varying emitter densities and
its potential to provide superior localization accuracy across a wide range of
imaging conditions.

Figures 3g to i illustrate the 3D efficiency of the two methods for high,
medium, and low SNRs, respectively. The results clearly demonstrate a
significant improvement in 3D efficiency by adopting the structural-based
training approach. On average, the performance of LUENN improved by 20% across
all three levels of SNRs. This enhancement in 3D efficiency showcases the
superiority of the structural-based training method in achieving more accurate
and reliable 3D reconstructions in single-molecule localization microscopy.

Figure 3:  Quantitative comparison of training methods, encompassing both
random and structural-based approaches, across varying signal-to-noise ratios
(SNRs) – high, medium, and low. a-c. Depicting the Jaccardian index and
volumetric RMSE as functions of frame densities. e-f. Illustrating the lateral
and axial RMSE trends relative to frame densities. g-i. Presenting the 3D
efficiency trends in relation to frame densities.

To visually assess the quality of the reconstructed Microtubules, we have
provided reconstruction of low density frames, nominal density equal to 0.38
emitters per frame, at high, medium, and low SNRS in Figures 4 a to f.
Notably, the structural-based training approach has demonstrated its
effectiveness in removing checkerboard artifacts, which are pixel-level biases
resulting in grid-like patterns in the reconstructed structures. These
artifacts can significantly impact the accuracy of 3D reconstructions and may
lead to misleading interpretations of biological structures.

Figure 4: Visual evaluation of reconstruction quality under low-density frame
conditions (with a nominal density of 0.38 emitters per frame) across diverse
signal-to-noise ratios (SNRs), encompassing high, medium, and low levels.
Panels a-b illustrate the reconstructions under high SNR, c-d depict the
reconstructions under medium SNR, and e-f showcase the reconstructions under
low SNR.

By successfully mitigating these checkerboard artifacts, the structural-based
training approach ensures a more reliable and accurate reconstruction of 3D
structures, thereby advancing the capabilities of SMLM in studying complex
biological systems. This improvement in reconstruction quality has important
implications for understanding the spatial organization of cellular components
and interactions within subcellular structures, contributing to further
breakthroughs in the field of super-resolution microscopy and its applications
in biological and medical research.

Finally, structure-based training does not negatively impact the localization
of isolated emitters. As Figure 3 shows, even at low emitter densities the
structure-based training method demonstrates significant improvement in both
localization accuracy and precision. This means that even in the absence of
multiple emitters in an image, i.e. when the neural network can’t utilize
additional information about structure, the neural network performs better at
localization.

##  4 Conclusion

In conclusion, our study has demonstrated the efficacy of the structural-based
training approach in significantly improving the performance of CNN-based
algorithms for single-molecule localization microscopy (SMLM) and 3D object
reconstruction. By utilizing two key metrics, the Jaccardian index as a
measure of localization accuracy (JI) and root-mean-square error (RMSE) as a
measure of precision, we have quantitatively shown the superiority of the
structural-based model over the traditional random-based training model.

The structural-based training approach exhibited remarkable improvements in
both detection rate and localization precision across a wide range of signal-
to-noise ratios (SNRs), outperforming the random-based trained model in high,
medium, and low SNR conditions. With an average of 20% higher detection rate
and 35% lower RMSE in high SNR, and 7.2% and 5.6% higher detection rates in
medium and low SNRs, respectively, the structural-based model showcases its
robustness and versatility. These advantages exist even at very low emitter
densities where the structure is not obvious in every image.

Notably, the structural-based training approach excelled in achieving superior
localization precision, especially in the depth (Z) direction, which is
crucial for accurate 3D object reconstruction. The increasing difference
between lateral and axial localization RMSE plots with higher nominal density
further highlights the method’s effectiveness in handling varying emitter
densities and enhancing localization accuracy.

The visual assessment of reconstructed Microtubules demonstrated that the
structural-based training approach effectively eliminated checkerboard
artifacts, a common issue affecting the accuracy of 3D reconstructions. This
improvement ensures more reliable and accurate representations of biological
structures, enhancing the capabilities of SMLM in studying complex subcellular
systems.

Overall, our findings suggest that the structural-based training approach
holds great promise for advancing the field of super-resolution microscopy and
its applications in biological and medical research. By improving localization
precision and reconstruction quality, this novel approach can lead to deeper
insights into the spatial organization of cellular components and
interactions, ultimately contributing to significant breakthroughs in
understanding complex biological processes. As a result, the structural-based
training approach can have a transformative impact on the study of biological
systems at the nanoscale, offering new avenues for exploration and
discoveries.

We acknowledge the Center for Computational Research at the University at
Buffalo for providing the computational support needed for training the models
and for supplying the results of this study.

## References

  * Abbe 1873 Abbe, E. Beiträge zur Theorie des Mikroskops und der mikroskopischen Wahrnehmung. _Archiv für mikroskopische Anatomie_ 1873, _9_ , 413–468
  * Owen and Gaus 2013 Owen, D. M.; Gaus, K. Imaging lipid domains in cell membranes: the advent of super-resolution fluorescence microscopy. _Frontiers in plant science_ 2013, _4_ , 503
  * Hell and Wichmann 1994 Hell, S. W.; Wichmann, J. Breaking the diffraction resolution limit by stimulated emission: stimulated-emission-depletion fluorescence microscopy. _Optics letters_ 1994, _19_ , 780–782
  * Gustafsson 2000 Gustafsson, M. G. Surpassing the lateral resolution limit by a factor of two using structured illumination microscopy. _Journal of microscopy_ 2000, _198_ , 82–87
  * Vobornik et al. 2008 Vobornik, D.; Banks, D. S.; Lu, Z.; Fradin, C.; Taylor, R.; Johnston, L. J. Fluorescence correlation spectroscopy with sub-diffraction-limited resolution using near-field optical probes. _Applied Physics Letters_ 2008, _93_ , 163904
  * Speiser et al. 2021 Speiser, A.; Müller, L.-R.; Hoess, P.; Matti, U.; Obara, C. J.; Legant, W. R.; Kreshuk, A.; Macke, J. H.; Ries, J.; Turaga, S. C. Deep learning enables fast and dense single-molecule localization with high accuracy. _Nature methods_ 2021, _18_ , 1082–1090
  * Marsh et al. 2018 Marsh, R. J.; Pfisterer, K.; Bennett, P.; Hirvonen, L. M.; Gautel, M.; Jones, G. E.; Cox, S. Artifact-free high-density localization microscopy analysis. _Nature methods_ 2018, _15_ , 689–692
  * Caetano et al. 2015 Caetano, F. A.; Dirk, B. S.; Tam, J. H.; Cavanagh, P. C.; Goiko, M.; Ferguson, S. S.; Pasternak, S. H.; Dikeakos, J. D.; de Bruyn, J. R.; Heit, B. MIiSR: molecular interactions in super-resolution imaging enables the analysis of protein interactions, dynamics and formation of multi-protein structures. _PLoS computational biology_ 2015, _11_ , e1004634
  * Aguet et al. 2005 Aguet, F.; Van De Ville, D.; Unser, M. A maximum-likelihood formalism for sub-resolution axial localization of fluorescent nanoparticles. _Optics Express_ 2005, _13_ , 10503–10522
  * Thompson et al. 2002 Thompson, R. E.; Larson, D. R.; Webb, W. W. Precise nanometer localization analysis for individual fluorescent probes. _Biophysical journal_ 2002, _82_ , 2775–2783
  * Boyd et al. 2018 Boyd, N.; Jonas, E.; Babcock, H.; Recht, B. DeepLoco: fast 3D localization microscopy using neural networks. _BioRxiv_ 2018, 267096
  * Nehme et al. 2020 Nehme, E.; Freedman, D.; Gordon, R.; Ferdman, B.; Weiss, L. E.; Alalouf, O.; Naor, T.; Orange, R.; Michaeli, T.; Shechtman, Y. DeepSTORM3D: dense 3D localization microscopy and PSF design by deep learning. _Nature methods_ 2020, _17_ , 734–740
  * Abdehkakha and Snoeyink 2023 Abdehkakha, A.; Snoeyink, C. Localization of Ultra-dense Emitters with Neural Networks. _arXiv preprint arXiv:2305.05542_ 2023,
  * Byth and Ripley 1980 Byth, K.; Ripley, B. On sampling spatial patterns by distance methods. _Biometrics_ 1980, 279–284


2420221187458

# Separating Layered Treewidth and
Row Treewidth††thanks: Research of Bose, Dujmović and Morin supported by
NSERC. Research of Wood supported by the Australian Research Council.

Prosenjit Bose1  Vida Dujmović 2  Mehrnoosh Javarsineh1
Pat Morin1  David R. Wood3  School of Computer Science, Carleton University,
Ottawa, Canada
School of Computer Science and Electrical Engineering, University of Ottawa,
Ottawa, Canada
School of Mathematics, Monash University, Melbourne, Australia

(2021-05-05; 2021-11-24; 2022-04-12)

###### Abstract

Layered treewidth and row treewidth are recently introduced graph parameters
that have been key ingredients in the solution of several well-known open
problems. In particular, the _layered treewidth_ of a graph $G$ is the minimum
integer $k$ such that $G$ has a tree-decomposition and a layering such that
each bag has at most $k$ vertices in each layer. The _row treewidth_ of $G$ is
the minimum integer $k$ such that $G$ is isomorphic to a subgraph of
$H\boxtimes P$ for some graph $H$ of treewidth at most $k$ and for some path
$P$. It follows from the definitions that the layered treewidth of a graph is
at most its row treewidth plus 1. Moreover, a minor-closed class has bounded
layered treewidth if and only if it has bounded row treewidth. However, it has
been open whether row treewidth is bounded by a function of layered treewidth.
This paper answers this question in the negative. In particular, for every
integer $k$ we describe a graph with layered treewidth 1 and row treewidth
$k$. We also prove an analogous result for layered pathwidth and row
pathwidth.

###### keywords:

treewidth, layered treewidth, row treewidth

##  1 Introduction

Treewidth is a graph parameter that measures how similar a given graph is to a
tree; it is of fundamental importance in structural and algorithmic graph
theory; see the surveys [3, 32, 23].

Layered treewidth is a variant of treewidth introduced independently by
Dujmović et al. [15] and Shahrokhi [37]; see Section 2 for the definition. A
key property is that layered treewidth is bounded on planar graphs but
treewidth is not. In particular, planar graphs have layered treewidth at most
3 [15], but the $n\times n$ grid graph has treewidth $n$. Layered treewidth
has been used in upper bounds on several graph parameters including queue-
number [15, 13], stack number [13], boxicity [36], clustered chromatic number
[28], generalised colouring numbers [26], asymptotic dimension [4], as well
for results in intersection graph theory [37].

Row treewidth111The name “row treewidth” is an original contribution of the
present paper. is a refinement of layered treewidth, implicitly introduced by
Dujmović et al. [14], who proved that planar graphs have row treewidth at most
8. This result and its generalisations have been the key to solving several
open problems, regarding queue-number [14], nonrepetitive chromatic number
[12], universal graphs [21, 5, 11], centred colouring [7], graph drawing [14,
31], and vertex ranking [6].

Layered and row treewidth are closely related in that the layered treewidth of
a graph is at most its row treewidth plus 1, and a minor-closed class has
bounded layered treewidth if and only if it has bounded row treewidth.
However, a fundamental open problem is whether row treewidth is bounded by a
function of layered treewidth. This paper answers this question in the
negative.

######  Theorem 1.

For each $k\in\mathbb{N}$ there is a graph with layered treewidth 1 and row
treewidth $k$.

This result is proved in Section 3. In Section 4 we use a key lemma from the
proof of Theorem 1 to prove a result about the relationship between layered
treewidth and queue-number.

Layered pathwidth is a graph parameter analogous to layered treewidth, first
studied by Bannister et al. [1] and Dujmović et al. [10]. Row pathwidth is
defined in a similar way to row treewidth. We prove the following analogue of
Theorem 1 for layered pathwidth and row pathwidth.

######  Theorem 2.

For each $k\in\mathbb{N}$ there is a tree with layered pathwidth 1 and row
pathwidth $k$.

##  2 Definitions

We consider finite, undirected, simple graphs and use standard graph theory
terminology [8].

#### Minors

A graph $H$ is a _minor_ of a graph $G$ if a graph isomorphic to $H$ can be
obtained from a subgraph of $G$ by contracting edges. A graph class
$\mathcal{G}$ is _minor-closed_ if for every graph $G\in\mathcal{G}$, every
minor of $G$ is in $\mathcal{G}$. A graph class $\mathcal{G}$ is _proper_ if
some graph is not in $\mathcal{G}$. A _$K_{t}$ model_ in a graph $G$ is a set
$\\{X_{1},\dots,X_{t}\\}$ of pairwise-disjoint connected subgraphs in $G$,
such that there is an edge of $G$ between $X_{i}$ and $X_{j}$ for all distinct
$i,j\in\\{1,\dots,t\\}$. Clearly, $K_{t}$ is a minor of $G$ if and only if $G$
contains a $K_{t}$ model.

#### Treewidth and Pathwidth

A _tree decomposition_ $\mathcal{T}$ of a graph $G$ is a collection
$(B_{x}:x\in V(T))$ of subsets of $V(G)$ called _bags_ indexed by the nodes of
a tree $T$ such that  (i) for each $v\in V(G)$, the induced subgraph
$T[\\{x\in V(T):v\in B_{x}\\}]$ is nonempty and connected; and  (ii) for each
edge $vw\in E(G)$, there exists $x\in V(T)$ such that $\\{v,w\\}\subseteq
B_{x}$.  The _width_ of a tree-decomposition is the size of its largest bag,
minus $1$. The _treewidth $\operatorname{tw}(G)$_ of a graph $G$ is the
minimum width of any tree-decomposition of $G$. If $\mathcal{P}=(B_{x}:x\in
V(P))$ is a tree-decomposition of $G$ and $P$ is a path, then $\mathcal{P}$ is
a _path-decomposition_ of $G$. The _pathwidth $\operatorname{pw}(G)$_ of a
graph $G$ is the minimum width of any path-decomposition of $G$. For each
$k\in\mathbb{N}$, the graphs with treewidth at most $k$ form a minor-closed
class, as do the graphs with pathwidth at most $k$. Note that
$\operatorname{tw}(K_{n})=\operatorname{pw}(K_{n})=n-1$.

### Layered Treewidth and Pathwidth

A _layering_ $\mathcal{L}$ of a graph $G$ is a partition of $V(G)$ into a
sequence of sets $(L_{0},L_{1},\ldots)$ such that for any edge $vw\in E(G)$,
if $v\in L_{i}$ and $w\in L_{j}$ then $|i-j|\leqslant 1$. For example, if $r$
is a vertex in a connected graph $G$, and $L_{i}$ is the set of vertices at
distance $i$ from $r$ in $G$, then $(L_{0},L_{1},\dots)$ is the _breadth-
first_ layering of $G$ rooted at $r$. A _layered tree-decomposition_ of a
graph $G$ consists of a pair $(\mathcal{L},\mathcal{T})$ where
$\mathcal{L}=(L_{0},L_{1},\ldots)$ is a layering of $G$ and
$\mathcal{T}=(B_{x}:x\in V(T))$ is a tree-decomposition of $G$. The (layered)
_width_ of $(\mathcal{L},\mathcal{T})$ is the size of the largest intersection
between a layer and a bag; that is, $\max\\{|B_{x}\cap L_{i}|:x\in
V(T),i\in\mathbb{N}_{0}\\}$. The _layered treewidth $\operatorname{ltw}(G)$_
of $G$ is the minimum width of any layered tree-decomposition of $G$.

This definition was introduced independently by Shahrokhi [37] and Dujmović et
al. [15]. The latter authors proved that $\operatorname{ltw}(G)\leqslant 3$
for every planar graph $G$; more generally that
$\operatorname{ltw}(G)\leqslant 2g+3$ for every graph $G$ of Euler genus $g$;
and that a minor-closed class $\mathcal{G}$ has bounded layered treewidth if
and only if some apex graph222A graph $G$ is _apex_ if $G-v$ is planar for
some vertex $v$. A graph $G$ is an _apex-forest_ if $G-v$ is a forest for some
vertex $v$. is not in $\mathcal{G}$. For an arbitrary proper minor-closed
class $\mathcal{G}$, Dujmović et al. [15] showed that every graph in
$\mathcal{G}$ has a tree-decomposition in which each bag has a bounded set of
vertices whose deletion leaves a subgraph with bounded layered treewidth. This
version of Robertson and Seymour’s Graph Minor Structure Theorem has proved to
be very useful [28, 27, 29, 4].

If $(\mathcal{L},\mathcal{P})$ is a layered tree-decomposition of $G$ and
$\mathcal{P}$ is a path-decomposition, then $(\mathcal{L},\mathcal{P})$ is a
_layered path-decomposition_ of $G$. The _layered pathwidth_ of $G$ is the
minimum width of any layered path-decomposition of $G$. This parameter was
introduced by Bannister et al. [1], who proved that every outerplanar graph
has layered pathwidth at most 2 (amongst other examples).

### Row Treewidth and Pathwidth

The _cartesian product_ of graphs $A$ and $B$, denoted by
$A\mathbin{\square}B$, is the graph with vertex set $V(A)\times V(B)$, where
distinct vertices $(v,x),(w,y)\in V(A)\times V(B)$ are adjacent if: $v=w$ and
$xy\in E(B)$; or $x=y$ and $vw\in E(A)$. The _direct product_ of $A$ and $B$,
denoted by $A\times B$, is the graph with vertex set $V(A)\times V(B)$, where
distinct vertices $(v,x),(w,y)\in V(A)\times V(B)$ are adjacent if $vw\in
E(A)$ and $xy\in E(B)$. The _strong product_ of $A$ and $B$, denoted by
$A\boxtimes B$, is the union of $A\mathbin{\square}B$ and $A\times B$.

The _row treewidth $\operatorname{rtw}(G)$_ of a graph $G$ is the minimum
treewidth of a graph $H$ such that $G$ is isomorphic to a subgraph of
$H\boxtimes P_{\infty}$, where $P_{\infty}$ is the 1-way infinite path. This
definition is implicit in the work of Dujmović et al. [14] who proved that
$\operatorname{rtw}(G)\leqslant 8$ for every planar graph $G$; more generally,
that $\operatorname{rtw}(G)\leqslant 2g+9$ for every graph $G$ of Euler genus
$g$; and that a minor-closed class $\mathcal{G}$ has bounded row treewidth if
and only if some apex graph is not in $\mathcal{G}$. For an arbitrary minor-
closed class $\mathcal{G}$, Dujmović et al. [14] showed that every graph in
$\mathcal{G}$ has a tree-decomposition in which each bag has a bounded set of
vertices whose deletion leaves a subgraph with bounded row treewidth.

It follows from the definitions that for every graph $G$,

$\operatorname{ltw}(G)\leqslant\operatorname{rtw}(G)+1.$

To see this, suppose that $G\subseteq H\boxtimes P_{\infty}$ where
$\operatorname{tw}(H)=\operatorname{rtw}(G)$. Let $\mathcal{T}=(B_{x}:x\in
V(T))$ be a minimum-width tree-decomposition of $H$. Assume
$V(P_{\infty})=\mathbb{N}$. For each $b\in\mathbb{N}$, let $L_{b}:=\\{(a,b)\in
V(G):a\in V(H)\\}$. So $\mathcal{L}=(L_{1},L_{2},\dots)$ is a layering of $G$.
For each $x\in V(T)$, let $B^{\prime}_{x}:=\\{(a,b)\in V(G):a\in V(H)\cap
B_{x},\,b\in\mathbb{N}\\}$. So $\mathcal{T^{\prime}}:=(B^{\prime}_{x}:x\in
V(T))$ is a tree-decomposition of $G$. Note that $|B^{\prime}_{x}\cap
L_{b}|\leqslant|B_{x}|\leqslant\operatorname{tw}(H)+1$. Thus
$(\mathcal{L},\mathcal{T})$ is a layered tree-decomposition of $G$ with width
at most $\operatorname{tw}(H)+1=\operatorname{rtw}(G)+1$.

Define the _row pathwidth_ $\operatorname{rpw}(G)$ of a graph $G$ to be the
minimum pathwidth of a graph $H$ such that $G$ is isomorphic to a subgraph of
$H\boxtimes P_{\infty}$. Then
$\operatorname{lpw}(G)\leqslant\operatorname{rpw}(G)+1$ for every graph $G$.
As explained above, “bounded layered treewidth” and “bounded row treewidth”
coincide for minor-closed classes. However, this is not the case for their
pathwidth analogues. Dujmović et al. [10] proved that a minor-closed class
$\mathcal{G}$ has bounded layered pathwidth if and only if some apex-forest is
not in $\mathcal{G}$. However, forests are a minor-closed class excluding some
apex-forest (namely, $K_{3}$), but forests have unbounded row pathwidth by
Theorem 2. In fact, Robertson and Seymour [33] proved that for every fixed
forest $T$, the class of $T$-minor-free graphs has bounded pathwidth (see [2]
for a tight bound). It follows that a minor-closed class $\mathcal{G}$ has
bounded row pathwidth if and only if $\mathcal{G}$ has bounded pathwidth if
and only if some tree is not in $\mathcal{G}$.

##  3 Separating Layered Treewidth and Row Treewidth

This section proves Theorem 1. Subdivisions play a key role. A _subdivision_
of a graph $G$ is a graph $G^{\prime}$ obtained by replacing each edge $vw$ of
$G$ with a path $P_{vw}$ from $v$ to $w$ whose internal vertices have degree
$2$. If each $P_{vw}$ has exactly $s$ internal vertices, then $G^{\prime}$ is
the _$s$ -subdivision_ of $G$. If each $P_{vw}$ has at most $s$ internal
vertices, then $G^{\prime}$ is a _$(\leqslant\\!s)$ -subdivision_ of $G$. It
is well known and easily proved that
$\operatorname{tw}(G^{\prime})=\operatorname{tw}(G)$ for every subdivision
$G^{\prime}$ of $G$.

The proof of Theorem 1 is based on two lemmas. The first shows that
subdivisions efficiently reduce layered treewidth (Lemma 3). The second shows
that subdivisions do not efficiently reduce row treewidth (Lemma 6). The
theorem quickly follows.

###  3.1 Subdivisions Efficiently Reduce Layered Treewidth

######  Lemma 3.

For every graph $G$ with layered treewidth $k\in\mathbb{N}$,

  1. (a)

there exists a $(\leqslant\\!2k-2)$-subdivision $G^{\prime}$ of $G$ of layered
treewidth 1; and

  2. (b)

if any subdivision $G^{\prime}$ of $G$ has layered treewidth at most $c$, then
some edge of $G$ is subdivided at least $k/c-1$ times in $G^{\prime}$.

###### Proof.

Let $(B_{x}:x\in V(T))$ be a tree-decomposition of $G$ and let
$(V_{0},V_{1},\dots)$ be a layering of $G$, such that $|B_{x}\cap
V_{i}|\leqslant k$ for each $x\in V(T)$ and $i\in\mathbb{N}_{0}$.

First we prove (a). We may assume that $B_{x}\cap V_{i}$ is a clique for each
$x\in V(T)$ and $i\in\mathbb{N}_{0}$. So $G[V_{i}]$ is a chordal graph with no
$(k+1)$-clique, which is therefore $k$-colourable. Let
$c:V(G)\to\\{0,1,\dots,k-1\\}$ be a function such that $c$ is a proper
$k$-colouring of $G[V_{i}]$ for each $i\in\mathbb{N}_{0}$. Thus for each $x\in
V(T)$ and $i\in\mathbb{N}_{0}$, and for all distinct vertices $v,w\in
B_{x}\cap V_{i}$, we have $c(v)\neq c(w)$. Let $L_{ki+j}:=\\{v\in
V_{i}:c(v)=j\\}$ for $i\in\mathbb{N}_{0}$ and $j\in\\{0,1,\dots,k-1\\}$. Let
$G^{\prime}$ be obtained from $G$ as follows. Consider each edge $e=vw$ of
$G$. Say $v\in V_{i}$ and $w\in V_{i^{\prime}}$, and $v\in L_{a}$ and $w\in
L_{a^{\prime}}$. Without loss of generality, $a<a^{\prime}$. Then
$a^{\prime}\leqslant k(i^{\prime}+1)-1\leqslant k(i+2)-1\leqslant a+2k-1$.
Replace $e$ by the path $(v,s_{e,a+1},s_{e,a+2},\dots,s_{e,a^{\prime}-1},w)$
in $G^{\prime}$. The number of division vertices is $a^{\prime}-1-a\leqslant
2k-2$. Put the division vertex $s_{e,b}$ in $L_{b}$ for each
$b\in\\{a+1,\dots,a^{\prime}-1\\}$. So $(L_{1},L_{2},\dots)$ is a layering of
$G^{\prime}$. Some bag $B_{x}$ contains $v$ and $w$. Add a leaf node to $T$
adjacent to $x$ with corresponding bag
$\\{v,s_{e,a+1},s_{e,a+2},\dots,s_{e,a^{\prime}-1},w\\}$. We obtain a tree-
decomposition of $G^{\prime}$ with at most one vertex in each layer and in
each bag. Hence $\operatorname{ltw}(G^{\prime})=1$.

We now prove (b). Suppose that some $(\leqslant\\!r)$-subdivision $G^{\prime}$
of $G$ has $\operatorname{ltw}(G^{\prime})\leqslant c$. Let $(B_{x}:x\in
V(T))$ be a tree-decomposition of $G^{\prime}$ and let $(V_{0},V_{1},\dots)$
be a layering of $G^{\prime}$ such that $|B_{x}\cap V_{i}|\leqslant c$ for
each $x\in V(T)$ and $i\in\mathbb{N}_{0}$. Orient each edge of $G$
arbitrarily. For each oriented edge $vw$ of $G$ and for each division vertex
$z$ of $vw$, let $\alpha(z):=v$. For each node $x\in V(T)$, let $C_{x}$ be
obtained from $B_{x}$ by replacing each division vertex $z\in B_{x}$ by
$\alpha(z)$. Observe that $(C_{x}:x\in V(T))$ is a tree-decomposition of $G$.
For $j\in\mathbb{N}_{0}$, let $L_{j}:=V(G)\cap(V_{j(r+1)}\cup
V_{j(r+1)+1}\cup\dots\cup V_{(j+1)(r+1)-1})$. Consider an edge $vw$ of $G$
with $v\in V_{i}$ and $w\in V_{i^{\prime}}$ and $i\leqslant i^{\prime}$. Then
$i^{\prime}\leqslant i+r+1$ since $vw$ is subdivided at most $r$ times. Say
$v\in L_{j}$ and $w\in L_{j^{\prime}}$. By definition, $j(r+1)\leqslant
i\leqslant(j+1)(r+1)-1$ and $j^{\prime}(r+1)\leqslant
i^{\prime}\leqslant(j^{\prime}+1)(r+1)-1$. Hence $j^{\prime}(r+1)\leqslant
i^{\prime}\leqslant i+r+1\leqslant(j+1)(r+1)-1+(r+1)=(j+1)(r+1)+r$, implying
$j^{\prime}\leqslant j+1$. That is, $(L_{0},L_{1},\dots)$ is a layering of
$G$. Each layer $L_{j}$ contains at most $c(r+1)$ vertices in each bag
$C_{x}$. Thus $k=\operatorname{ltw}(G)\leqslant c(r+1)$, implying $r\geqslant
k/c-1$. ∎

Note that the proof of Lemma 3(a) is easily adapted to show that if
$s_{e}\geqslant 2k-2$ for each edge $e\in E(G)$ and $G^{\prime}$ is the
subdivision of $G$ in which each edge $e$ is subdivided $s_{e}$ times, then
$\operatorname{ltw}(G^{\prime})\leqslant 2$. We omit these straightforward
details.

Bannister et al. [1] proved that
$\operatorname{lpw}(G)\leqslant{\lceil(\operatorname{pw}(G)+1)/2\rceil}$. An
analogous proof shows that
$\operatorname{ltw}(G)\leqslant{\lceil(\operatorname{tw}(G)+1)/2\rceil}$.
Lemma 3(a) then implies:

######  Corollary 4.

Every graph with treewidth $k$ has a $(\leqslant k)$-subdivision with layered
treewidth 1.

We remark that Corollary 4 is tight, up to a small constant factor:

######  Observation 5.

Let $G^{\prime}$ be any $(\leqslant\\!s)$-subdivision of the complete graph
$K_{k+1}$. Then $\operatorname{ltw}(G^{\prime})\geqslant(k+1)/(2s+3)$. In
particular, $\operatorname{ltw}(G^{\prime})>1$ if $s<(k-2)/2$.

###### Proof.

Let $(\mathcal{L},\mathcal{T})$ be a layered tree-decomposition of
$G^{\prime}$. Since $K_{k+1}$ has radius 1, $G^{\prime}$ has radius at most
$s+1$ and therefore $|\mathcal{L}|\leqslant 2s+3$. Since $K_{k+1}$ has
treewidth $k$, so does $G^{\prime}$. Thus $\mathcal{T}$ has at least one bag
$B_{x}$ of size at least $k+1$. By the pigeonhole principle, $|B_{x}\cap
L|\geqslant(k+1)/\mathcal{|L|}\geqslant(k+1)/(2s+3)$ for at least one
$L\in\mathcal{L}$. ∎

###  3.2 Subdivisions do not Efficiently Reduce Row Treewidth

This section proves the following result.

######  Lemma 6.

For each $k\in\mathbb{N}$ and $s\in\mathbb{N}_{0}$ there exists a graph $G$
such that for every $(\leqslant\\!s)$-subdivision $G^{\prime}$ of $G$,

$\operatorname{rtw}(G^{\prime})\geqslant k\geqslant\operatorname{tw}(G).$

A weaker version (with a more indirect proof) of Lemma 6 is implied by
existing results about the _$p$ -centred chromatic number $\chi_{p}(G)$_ of a
graph $G$; see [7, 9] for the definition (we will not need it). Dubois et al.
[9] show that, for each $p\in\mathbb{N}$, there exists an integer
$k\in\Theta(\sqrt{p})$ and a treewidth-$k$ graph $G$, such that if
$G^{\prime}$ is the $6k$-subdivision of $G$, then

$\chi_{p}(G^{\prime})\geqslant 2^{\Omega(\operatorname{tw}(G))}.$

On the other hand, Dȩbski et al. [7] (see also [16]) show that for every graph
$G$ and $p\in\mathbb{N}$,

$\chi_{p}(G)\leqslant(p+1)p^{\binom{p+\operatorname{rtw}(G)}{\operatorname{rtw}(G)}}.$

Thus, for the graph $G^{\prime}$ constructed by Dubois et al. [9],

$2^{\Omega(\operatorname{tw}(G))}\leqslant\chi_{p}(G^{\prime})\leqslant(p+1)p^{\binom{p+\operatorname{rtw}(G^{\prime})}{\operatorname{rtw}(G^{\prime})}}.$

This implies that
$\operatorname{rtw}(G^{\prime})\in\Omega(\operatorname{tw}(G)/\log(\operatorname{tw}(G)))$,
as noted in [19].

To prove Lemma 6 it will be convenient to use the language of $H$-partitions
from [14]. An _$H$ -partition_ of a graph $G$ is a partition
$\mathcal{H}=(B_{x}:x\in V(H))$ of $V(G)$ indexed by the nodes of some graph
$H$ such that for any edge $vw\in E(G)$, if $v\in B_{x}$ and $w\in B_{y}$,
then $xy\in E(H)$ or $x=y$. A _layered $H$-partition_
$(\mathcal{H},\mathcal{L})$ of a graph $G$ consists of an $H$-partition
$\mathcal{H}$ and a layering $\mathcal{L}$ of $G$. The (layered) _width_ of
$(\mathcal{H},\mathcal{L})$ is $\max\\{|B_{x}\cap L|:x\in
V(H),L\in\mathcal{L}\\}$. The _layered width_ of an $H$-partition
$\mathcal{H}$ of a graph $G$ is the minimum width, taken over all layerings
$\mathcal{L}$ of $G$, of the width of $(\mathcal{H},\mathcal{L})$. Dujmović et
al. [14] observed that:

######  Observation 7 ([14]).

For all graphs $G$ and $H$, $G$ is isomorphic to a subgraph of $H\boxtimes
P_{\infty}\boxtimes K_{w}$ if and only if $G$ has an $H$-partition of layered
width at most $w$. In particular, $\operatorname{rtw}(G)$ equals the minimum
treewidth of a graph $H$ for which $G$ has a layered $H$-partition of layered
width $1$.

This observation and the next lemma (with $w=1$) implies Lemma 6. Lemma 8
generalises a result of Dujmović et al. [14] who proved the $s=0$ case.

######  Lemma 8.

For all $w,k\in\mathbb{N}$ and $s\in\mathbb{N}_{0}$, there exists a graph
$G=G_{s,k,w}$ such that $\operatorname{tw}(G)\leqslant k$, and for any
$(\leqslant\\!s)$-subdivision $G^{\prime}$ of $G$, and for any graph $H$ and
any $H$-partition of $G^{\prime}$ with layered width at most $w$, there is a
$K_{k+1}$ minor in $H$, implying $\operatorname{tw}(H)\geqslant k$ and
$\operatorname{rtw}(G)\geqslant k$.

Say a $K_{k}$ model $\\{Y_{1},\dots,Y_{k}\\}$ in a graph $G$ _respects_ an
$H$-partition $(A_{x}:x\in V(H))$ of $G$ if for each $x\in V(H)$ there is at
most one value of $i\in\\{1,\dots,k\\}$ for which $V(Y_{i})\cap
A_{x}\neq\emptyset$. For each $i\in\\{1,\dots,k\\}$, let $X_{i}$ be the
subgraph of $H$ induced by those vertices $x\in V(H)$ such that $V(Y_{i})\cap
A_{x}\neq\emptyset$. Then $\\{X_{1},\dots,X_{k}\\}$ is a $K_{k}$ model in $H$.
Thus the next lemma implies Lemma 8.

######  Lemma 9.

For all $w\in\mathbb{N}$ and $k,s\in\mathbb{N}_{0}$, there exists a graph
$G=G_{s,k,w}$ such that $\operatorname{tw}(G)\leqslant k$, and for any
$(\leqslant\\!s)$-subdivision $G^{\prime}$ of $G$, and for any graph $H$ and
any $H$-partition $(A_{x}:x\in V(H))$ of $G^{\prime}$ with layered width at
most $w$, there is a model $\\{Y_{1},\dots,Y_{k+1}\\}$ of $K_{k+1}$ in
$G^{\prime}$ that respects $(A_{x}:x\in V(H))$, and for each
$i\in\\{1,\dots,k+1\\}$ we have $|V(Y_{i})|\leqslant k(2s+1)+1$ and
$V(Y_{i})\cap V(G)\neq\emptyset$.

###### Proof.

The proof is by induction on $k$. For the base case with $k=0$, let
$G_{s,0,w}$ be the graph with one vertex $v$ and no edges. Any subdivision
$G^{\prime}$ contains a model $Y_{1}=G^{\prime}[\\{v\\}]$ of $K_{1}$ with
$|Y_{1}|\leqslant 1=0(2s+1)+1$, and this model trivially respects any
$H$-partition of $G^{\prime}$, for any graph $H$.

Now assume $k\geqslant 1$, and that the induction hypothesis holds for $k-1$.
Let $Q=G_{s,k-1,w}$ be the graph obtained by induction. Let
$N:=k^{2}(2s+1)(4s+5)w+1$. Create the graph $G$ by starting with $N$ disjoint
copies $Q_{1},\ldots,Q_{N}$ of $Q$. Next add a vertex $v$ and, for each
$i\in\\{1,\ldots,N\\}$ and each $u\in V(Q_{i})$, add $N$ internally disjoint
paths of length $2$ from $v$ to $u$.

First we show that $\operatorname{tw}(G)\leqslant k$. If $k=1$ then $G$ is a
subdivided star, which has treewidth 1. Now assume that $k\geqslant 2$. Begin
with any tree-decomposition $(B_{x}:x\in V(T))$ of $Q_{1}\cup\ldots\cup Q_{N}$
with width at most $(k-1)$. Add $v$ to every bag $B_{x}$. For all
$i,j\in\\{1,\ldots,N\\}$ and for each vertex $u\in V(Q_{i})$, choose a bag
$B_{x}$ that contains $u$, and attach a leaf node adjacent to $x$ whose bag
contains $v$, $u$, and the degree-2 vertex of the $j$-th length-2 path from
$v$ to $u$. Each bag of this decomposition has size at most
$\max\\{3,k+1\\}\leqslant k+1$ and therefore $\operatorname{tw}(G)\leqslant
k$.

Let $G^{\prime}$ be a $(\leqslant\\!s)$-subdivision of $G$. Let $H$ be a graph
and let $(\mathcal{H},\mathcal{L})$ be a layered $H$-partition of $G^{\prime}$
with width at most $w$, where $\mathcal{H}:=(A_{x}:x\in V(H))$. Since the
radius of $G$ is $2$, the radius of $G^{\prime}$ is at most $2s+2$. Therefore
$|\mathcal{L}|\leqslant 4s+5$, and $|A_{x}|\leqslant(4s+5)w$ for each $x\in
V(H)$.

Let $z$ be the unique node of $H$ such that $v\in A_{z}$, and let
$Q^{\prime}_{1},\ldots,Q^{\prime}_{N}$ be the (possibly subdivided) copies of
$Q_{1},\ldots,Q_{N}$ that appear in $G^{\prime}$. So $A_{z}\cap
V(Q^{\prime}_{i})\neq\emptyset$ for at most $(4s+5)w-1$ values of
$i\in\\{1,\dots,N\\}$. Since $N\geqslant(4s+5)w$, we have
$V(Q^{\prime}_{i})\cap A_{z}=\emptyset$ for some $i\in\\{1,\ldots,N\\}$.

Let $H_{i}$ be the subgraph of $H$ induced by the nodes $\tau\in V(H)$ such
that $A_{\tau}\cap V(Q^{\prime}_{i})\neq\emptyset$. So $(A_{\tau}\cap
V(Q^{\prime}_{i}):\tau\in V(H_{i}))$ defines a width-$w$ layered
$H_{i}$-partition of $Q^{\prime}_{i}$ (with respect to layering
$\mathcal{L}$). By induction, there is a $K_{k}$ model
$\\{Y_{1},\dots,Y_{k}\\}$ in $G^{\prime}$ that respects $(A_{\tau}\cap
V(Q^{\prime}):\tau\in V(H_{i}))$, and for each $j\in\\{1,\dots,k\\}$ we have
$|V(Y_{j})|\leqslant(k-1)(2s+1)+1\leqslant k(2s+1)$ and $V(Y_{j})\cap
V(G)\neq\emptyset$. Let $y_{j}$ be a vertex in $V(Y_{j})\cap V(G)$. Note that
$|V(Y_{1}\cup\dots\cup Y_{k})|\leqslant k^{2}(2s+1)$. Let
$F:=\bigcup\\{A_{x}:A_{x}\cap V(Y_{1}\cup\dots\cup Y_{k})\neq\emptyset\\}$. So
$|F|\leqslant k^{2}(2s+1)(4s+5)w$.

Since $V(Q^{\prime}_{i})\cap A_{z}=\emptyset$, we have $v\not\in F$. Since
$N>|F|$, for each $j\in\\{1,\dots,k\\}$, for at least one of the $N$ paths
between $v$ and $y_{j}$ added in the construction of $G$, the corresponding
path in $G^{\prime}$ avoids $F$. Let $P_{j}$ be this path, not including
$y_{j}$. Let $Y_{k+1}:=\bigcup\\{P_{j}:j\in\\{1,\dots,k\\}\\}$. So
$V(Y_{k+1})\cap F=\emptyset$. By construction, there is an edge from $y_{j}$
to $Y_{k+1}$ for each $j\in\\{1,\dots,k\\}$. So $\\{Y_{1},\dots,Y_{k+1}\\}$ is
a $K_{k+1}$ model in $G^{\prime}$. Since $\\{Y_{1},\dots,Y_{k}\\}$ respects
$(A_{\tau}\cap V(Q^{\prime}):\tau\in V(H_{i}))$ and $V(Y_{k+1})\cap
F=\emptyset$, it follows that $\\{Y_{1},\dots,Y_{k+1}\\}$ respects
$(A_{x}:x\in V(H))$. By construction, $|V(Y_{k+1})|\leqslant k(2s+1)+1$ and
$v\in V(Y_{k+1})\cap V(G)$. By assumption, for each $j\in\\{1,\dots,k\\}$ we
have $|V(Y_{j})|\leqslant(k-1)(2s+1)+1$ and $V(Y_{j})\cap V(G)\neq\emptyset$.
This shows that $\\{Y_{1},\dots,Y_{k+1}\\}$ is the desired $K_{k+1}$ model in
$G^{\prime}$. ∎

We now prove the following strengthening of Theorem 1.

######  Theorem 10.

For each $k\in\mathbb{N}$ there is a graph $G$ with $\operatorname{ltw}(G)=1$
and $\operatorname{rtw}(G)=\operatorname{tw}(G)=k$.

###### Proof.

By Lemma 6 with $s=k$, there is a graph $G$ with
$\operatorname{tw}(G)\leqslant k$ such that
$\operatorname{rtw}(G^{\prime})\geqslant k$ for every
$(\leqslant\\!k)$-subdivision $G^{\prime}$ of $G$. By Corollary 4, there
exists a $(\leqslant\\!k)$-subdivision $G^{\prime}$ of $G$ with
$\operatorname{ltw}(G^{\prime})=1$. By definition,
$\operatorname{rtw}(H)\leqslant\operatorname{tw}(H)$ for every graph $H$. It
is well known and easily proved that
$\operatorname{tw}(H)=\operatorname{tw}(H^{\prime})$ for every subdivision
$H^{\prime}$ of $H$. Thus
$k\leqslant\operatorname{rtw}(G^{\prime})\leqslant\operatorname{tw}(G^{\prime})=\operatorname{tw}(G)\leqslant
k$, implying $\operatorname{rtw}(G)=\operatorname{tw}(G^{\prime})=k$. ∎

See [22, 9] for other examples where $O(\operatorname{tw}(G))$-subdivisions of
graphs $G$ are used to prove lower bounds.

##  4 Queue Layouts and Layered Treewidth

The _queue-number $\operatorname{qn}(G)$_ of a graph $G$ is a well-studied
graph parameter introduced by Heath, Leighton and Rosenberg [24, 25]; we omit
the definition since we will not need it. Queue-number can be upper bounded in
terms of layered treewidth and row treewidth. In particular, Dujmović et al.
[15] proved that $n$-vertex graphs of bounded layered treewidth have queue-
number in $O(\log n)$, while Dujmović et al. [14] proved that graphs of
bounded row treewidth have bounded queue-number. (Row treewidth was discovered
as a tool for proving that planar graphs have bounded queue-number.) This is a
prime example of a difference in behaviour between layered treewidth and row
treewidth. Nevertheless, it is open whether graphs of bounded layered
treewidth have bounded queue-number. We show that the answer to this question
depends entirely on the case of layered treewidth 1.

######  Corollary 11.

Graphs of bounded layered treewidth have bounded queue-number if and only if
graphs of layered treewidth 1 have bounded queue-number.

###### Proof.

The forward implication is immediate. Now assume that every graph of layered
treewidth 1 has queue-number at most some constant $c$. Let $G$ be a graph
with layered treewidth $k$. By Lemma 3, $G$ has a $(\leqslant k)$-subdivision
$G^{\prime}$ with layered treewidth 1. So
$\operatorname{qn}(G^{\prime})\leqslant c$. Dujmović and Wood [18] proved that
for every graph $H$ and $(\leqslant s)$-subdivision $H^{\prime}$ of $H$, we
have $\operatorname{qn}(H)\in O(\operatorname{qn}(H^{\prime})^{2s})$. This
bound was improved to $O(\operatorname{qn}(H^{\prime})^{s+1})$ in [17]. Thus
$\operatorname{qn}(G)\leqslant O(c^{k+1})$, implying that graphs of bounded
layered treewidth have bounded queue-number. ∎

This proof highlights the value of considering the behaviour of a graph
parameter on subdivisions. An analogous result holds for nonrepetitive
chromatic number $\pi(G)$ (using a result of Nešetřil et al. [30] to bound
$\pi(H)$ in terms of $\pi(H^{\prime})$).

######  Corollary 12.

Graphs of bounded layered treewidth have bounded nonrepetitive chromatic
number if and only if graphs of layered treewidth 1 have bounded nonrepetitive
chromatic number.

##  5 Separating Layered Pathwidth and Row Pathwidth

Recall that Theorem 2 asserts that for all $k\in\mathbb{N}$ there is a tree
$T$ with $\operatorname{lpw}(T)=1$ and $\operatorname{rpw}(T)\geqslant k$. We
first show that this theorem, in fact, follows from results in the literature.
Bannister et al. [1] noted that $\operatorname{lpw}(T)=1$ for every tree $T$.
Dvorák et al. [19] showed that any family $\mathcal{G}$ of graphs with bounded
row pathwidth has polynomial growth. The family of complete binary trees does
not have polynomial growth, so for each $k\in\mathbb{N}$, there exists a
complete binary tree $T$ with $\operatorname{rpw}(T)\geqslant k$. This proves
Theorem 2.

We now prove the following stronger result.

######  Theorem 13.

For every $k\in\mathbb{N}$ there exists a tree $T$ with
$\operatorname{pw}(T)=\operatorname{rpw}(T)=k$.

Let $T_{d,h}$ be the complete $d$-ary tree of height $h$. It is folklore that
$\operatorname{pw}(T_{d,h})=h$ for all $d\geqslant 3$ (see [34, 20, 35]). So
Observation 7 and 14 with $\ell=3$ and $w=1$ implies Theorem 13.

######  Lemma 14.

For all $h\in\mathbb{N}_{0}$ and $w,\ell\in\mathbb{N}$ there exists
$d\in\mathbb{N}$ such that for every graph $H$ and every $H$-partition
$(A_{x}:x\in V(H))$ of $T_{d,h}$ with layered width at most $w$, the graph $H$
contains a subgraph isomorphic to $T_{\ell,h}$. Moreover, if $r$ is the root
vertex of $T_{d,h}$ and $r\in A_{z}$, then $z$ is the root vertex of a
subgraph of $H$ isomorphic to $T_{\ell,h}$.

###### Proof.

We proceed by induction on $h$. The case $h=0$ is trivial. Now assume that
$h\geqslant 1$. We may assume that the number of layers is at most the
diameter of $T_{d,h}$ plus 1, which equals $2h+1$. So $|A_{x}|\leqslant
w(2h+1)$ for each $x\in V(H)$. Let $r_{1},\dots,r_{d}$ be the children of $r$
in $T_{d,h}$. Let $T^{1},\dots,T^{d}$ be the copies of $T_{d,h-1}$ in
$T_{d,h}$, where $T^{i}$ is rooted at $r_{i}$. At most $w(2h+1)-1$ of
$T^{1},\dots,T^{d}$ intersect $A_{z}$. Without loss of generality,
$T^{1},\dots,T^{d-w(2h+1)+1}$ do not intersect $A_{z}$. For each
$i\in\\{1,\dots,d-w(2h+1)+1\\}$, let $z_{i}$ be the vertex of $H$ such that
$r_{i}\in A_{z_{i}}$. Since $T^{i}\cap A_{z}=\emptyset$, we have $z_{i}\neq
z$. Since $rr_{i}\in E(T_{d,h})$, we have $zz_{i}\in E(H)$. By induction,
$H-z$ contains a subgraph $S^{i}$ isomorphic to $T_{\ell,h-1}$ rooted at
$z_{i}$. Let $X$ be the intersection graph of $S^{1},\dots,S^{d-w(2h+1)+1}$.
If $S^{i}$ and $S^{j}$ intersect in node $y$ of $H$, then $T^{i}$ and $T^{j}$
both intersect $A_{y}$. Since $|V(S^{i})|\leqslant(\ell+1)^{h-1}$ and
$|A_{y}|\leqslant w(2h+1)$, $X$ has maximum degree $\Delta(X)\leqslant
w(2h+1)(\ell+1)^{h}$. Thus $\chi(X)\leqslant w(2h+1)(\ell+1)^{h}+1$. For
sufficiently large $d$, we have $|V(X)|>(\ell-1)\chi(X)$. Thus, in any
$\chi(X)$-colouring of $X$, some colour class has at least $\ell$ vertices.
Without loss of generality, $S^{1},\dots,S^{\ell}$ are pairwise-disjoint.
Hence, $S_{1}\cup\dots\cup S_{\ell}$ along with $z$ forms a subgraph of $H$
isomorphic to $T_{\ell,h}$, rooted at $z$, as desired. ∎

We finish with an open problem: what is $\operatorname{rpw}(T_{2,h})$? It
follows from a result of Dvorák et al. [19] that
$\operatorname{rpw}(T_{2,h})\in\Omega(\frac{h}{\log h})$. Is this tight, or is
$\operatorname{rpw}(T_{2,h})\in\Omega(h)$? Obviously
$\operatorname{rpw}(T_{2,h})\leqslant\operatorname{pw}(T_{2,h})={\lceil\frac{h}{2}\rceil}$.

###### Acknowledgements.

Thanks to Robert Hickingbotham and to both referees for several helpful
comments.

## References

  * Bannister et al. [2019] Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, and David R. Wood.  Track layouts, layered path decompositions, and leveled planarity.  _Algorithmica_ , 81(4):1561–1583, 2019.
  * Bienstock et al. [1991] Dan Bienstock, Neil Robertson, Paul D. Seymour, and Robin Thomas.  Quickly excluding a forest.  _J. Combin. Theory Ser. B_ , 52(2):274–283, 1991.
  * Bodlaender [1998] Hans L. Bodlaender.  A partial $k$-arboretum of graphs with bounded treewidth.  _Theoret. Comput. Sci._ , 209(1-2):1–45, 1998.
  * Bonamy et al. [2021] Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, and Alex Scott.  Asymptotic dimension of minor-closed families and Assouad–Nagata dimension of surfaces.  _J. European Math. Soc._ , 2021.  arXiv:2012.02435.
  * Bonamy et al. [2020] Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk.  Shorter labeling schemes for planar graphs.  In Shuchi Chawla, ed., _Proc. ACM-SIAM Symp. on Discrete Algorithms(SODA ’20)_, pp. 446–462. 2020.  arXiv:1908.03341.
  * Bose et al. [2020] Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, and Pat Morin.  Asymptotically optimal vertex ranking of planar graphs.  arXiv:2007.06455, 2020.
  * Dȩbski et al. [2021] Michał Dȩbski, Stefan Felsner, Piotr Micek, and Felix Schröder.  Improved bounds for centered colorings.  _Advances in Combinatorics_ , 8, 2021.
  * Diestel [2012] Reinhard Diestel.  Graph theory, 4th edition, vol. 173 of _Graduate texts in mathematics_.  Springer, 2012.
  * Dubois et al. [2020] Loïc Dubois, Gwenaël Joret, Guillem Perarnau, Marcin Pilipczuk, and François Pitois.  Two lower bounds for $p$-centered colorings.  _Discret. Math. Theor. Comput. Sci._ , 22(4), 2020.
  * Dujmović et al. [2020] Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood.  Minor-closed graph classes with bounded layered pathwidth.  _SIAM J. Disc. Math._ , 34(3):1693–1709, 2020.
  * Dujmović et al. [2021] Vida Dujmović, Louis Esperet, Gwenaël Joret, Cyril Gavoille, Piotr Micek, and Pat Morin.  Adjacency labelling for planar graphs (and beyond).  _J. ACM_ , 68(6):42, 2021.
  * Dujmović et al. [2020a] Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David R. Wood.  Planar graphs have bounded nonrepetitive chromatic number.  _Advances in Combinatorics_ , 5, 2020a.
  * Dujmović and Frati [2018] Vida Dujmović and Fabrizio Frati.  Stack and queue layouts via layered separators.  _J. Graph Algorithms Appl._ , 22(1):89–99, 2018.
  * Dujmović et al. [2020b] Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood.  Planar graphs have bounded queue-number.  _J. ACM_ , 67(4):22, 2020b.
  * Dujmović et al. [2017] Vida Dujmović, Pat Morin, and David R. Wood.  Layered separators in minor-closed graph classes with applications.  _J. Combin. Theory Ser. B_ , 127:111–147, 2017.
  * Dujmović et al. [2019] Vida Dujmović, Pat Morin, and David R. Wood.  Graph product structure for non-minor-closed classes.  arXiv:1907.05168, 2019.
  * Dujmović et al. [2019] Vida Dujmović, Pat Morin, and David R. Wood.  Queue layouts of graphs with bounded degree and bounded genus.  arXiv:1901.05594, 2019.
  * Dujmović and Wood [2005] Vida Dujmović and David R. Wood.  Stacks, queues and tracks: Layouts of graph subdivisions.  _Discrete Math. Theor. Comput. Sci._ , 7:155–202, 2005.
  * Dvorák et al. [2021] Zdenek Dvorák, Tony Huynh, Gwenaël Joret, Chun-Hung Liu, and David R. Wood.  Notes on graph product structure theory.  In David R. Wood, Jan de Gier, Cheryl E. Praeger, and Terence Tao, eds., _2019-20 MATRIX Annals_ , pp. 513–533. Springer, 2021.
  * Ellis et al. [1994] John A. Ellis, I. Hal Sudborough, and Jonathan S. Turner.  The vertex separation and search number of a graph.  _Inform. and Comput._ , 113(1):50–79, 1994.
  * Esperet et al. [2020] Louis Esperet, Gwenaël Joret, and Pat Morin.  Sparse universal graphs for planarity.  2020\.  arXiv:2010.05779.
  * Grohe et al. [2018] Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos.  Coloring and covering nowhere dense graphs.  _SIAM J. Discrete Math._ , 32(4):2467–2481, 2018.
  * Harvey and Wood [2017] Daniel J. Harvey and David R. Wood.  Parameters tied to treewidth.  _J. Graph Theory_ , 84(4):364–385, 2017.
  * Heath et al. [1992] Lenwood S. Heath, F. Thomson Leighton, and Arnold L. Rosenberg.  Comparing queues and stacks as mechanisms for laying out graphs.  _SIAM J. Discrete Math._ , 5(3):398–412, 1992.
  * Heath and Rosenberg [1992] Lenwood S. Heath and Arnold L. Rosenberg.  Laying out graphs using queues.  _SIAM J. Comput._ , 21(5):927–958, 1992.
  * van den Heuvel and Wood [2018] Jan van den Heuvel and David R. Wood.  Improper colourings inspired by Hadwiger’s conjecture.  _J. London Math. Soc._ , 98:129–148, 2018.  arXiv:1704.06536.
  * Liu and Wood [2019a] Chun-Hung Liu and David R. Wood.  Clustered coloring of graphs excluding a subgraph and a minor.  2019a, arXiv:1905.09495.
  * Liu and Wood [2019b] Chun-Hung Liu and David R. Wood.  Clustered graph coloring and layered treewidth.  2019b, arXiv:1905.08969.
  * Liu and Wood [2019c] Chun-Hung Liu and David R. Wood.  Clustered variants of Hajós’ conjecture.  _J. Combin. Theory, Ser. B_ , 152:27–54, 2019c.
  * Nešetřil et al. [2011] Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R. Wood.  Characterisations and examples of graph classes with bounded expansion.  _European J. Combin._ , 33(3):350–373, 2011.
  * Pupyrev [2020] Sergey Pupyrev.  Improved bounds for track numbers of planar graphs.  _J. Graph Algorithms Appl._ , 24(3):323–341, 2020.
  * Reed [2003] Bruce A. Reed.  Algorithmic aspects of tree width.  In _Recent advances in algorithms and combinatorics_ , vol. 11, pp. 85–107. Springer, 2003.
  * Robertson and Seymour [1983] Neil Robertson and Paul Seymour.  Graph minors. I. Excluding a forest.  _J. Combin. Theory Ser. B_ , 35(1):39–61, 1983.
  * Scheffler [1990] Petra Scheffler.  A linear algorithm for the pathwidth of trees.  In Rainer Bodendiek and Rudolf Henn, eds., _Topics in combinatorics and graph theory_ , pp. 613–620. Physica, 1990.
  * Scheffler [1992] Petra Scheffler.  Optimal embedding of a tree into an interval graph in linear time.  In Jaroslav Nešetřil and Miroslav Fiedler, eds., _4th Czechoslovakian Symp. on Combinatorics, Graphs and Complexity_ , vol. 51 of _Annals of Discrete Mathematics_ , pp. 287–291. Elsevier, 1992\.
  * Scott and Wood [2020] Alex Scott and David R. Wood.  Better bounds for poset dimension and boxicity.  _Trans. Amer. Math. Soc._ , 373(3):2157–2172, 2020.
  * Shahrokhi [2013] Farhad Shahrokhi.  New representation results for planar graphs.  In _Proc. 29th European Workshop on Computational Geometry(EuroCG ’13)_, pp. 177–180. 2013.  arXiv:1502.06175.