# An improved planar graph product structure theorem

@article{Ueckerdt2021AnIP, title={An improved planar graph product structure theorem}, author={Torsten Ueckerdt and David R. Wood and Wendy Yi}, journal={ArXiv}, year={2021}, volume={abs/2108.00198} }

Dujmović, 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 G ⊆ H P . We improve this result by replacing “treewidth at most 8” by “simple treewidth at most 6”.

#### 2 Citations

Shallow Minors, Graph Products and Beyond Planar Graphs

- Mathematics
- 2021

The planar graph product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] states that every planar graph is a subgraph of the strong product of a graph with… Expand

Structural Properties of Graph Products

- Mathematics
- 2021

Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] established that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. Motivated by this… Expand

#### References

SHOWING 1-10 OF 25 REFERENCES

Planar Graphs have Bounded Queue-Number

- Computer Science, Mathematics
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

It is proved that every proper minor-closed class of graphs has bounded queue-number, and it is shown that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Expand

Separating layered treewidth and row treewidth

- Computer Science, Mathematics
- ArXiv
- 2021

This paper answers the question in the negative whether row treewidth is bounded by a function of layered Treewidth and proves an analogous result for layered pathwidth and row pathwidth. Expand

Adjacency Labelling for Planar Graphs (and Beyond)

- Computer Science, Mathematics
- 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
- 2020

The results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and <tex>$k$-planar graphs. Expand

Asymptotically Optimal Vertex Ranking of Planar Graphs

- Computer Science, Mathematics
- ArXiv
- 2020

New sublogarithmic upper bounds on the number of colours needed for $\ell$-rankings of apex minor-free graphs and $k$-planar graphs are obtained and these upper bounds are constructive and give $O(n\log n)$-time algorithms. Expand

Clustered 3-colouring graphs of bounded degree

- Mathematics
- 2020

A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are… Expand

Improved bounds for centered colorings

- Mathematics, Computer Science
- SODA
- 2020

Upper bounds for the maximum number of colors needed in a $p$-centered coloring of graphs from several widely studied graph classes are given. Expand

Shorter Labeling Schemes for Planar Graphs

- Computer Science, Mathematics
- SODA
- 2020

This work designs a labeling scheme with labels of bit length that generalizes to graphs of bounded Euler genus with the same label length up to a second-order term, improving the previous best upper bound of $n^{2+o(1)}$. Expand

Sparse universal graphs for planarity

- Mathematics, Computer Science
- ArXiv
- 2020

We show that for every integer $n\geq 1$ there exists a graph $G_n$ with $n^{1 + o(1)}$ edges such that every $n$-vertex planar graph is isomorphic to a subgraph of $G_n$. The best previous bound on… Expand

Planar graphs have bounded nonrepetitive chromatic number

- Mathematics, Computer Science
- ArXiv
- 2019

It is shown that planar graphs have nonrepetitive colourings with a bounded number of colours, thus proving a conjecture of Alon, Grytczuk, Haluszczak and Riordan (2002), and this result is generalised for graphs of bounded Euler genus, graphs excluding a fixed minor, and graphsexcluding a fixed topological minor. Expand

Polynomial bounds for centered colorings on proper minor-closed graph classes

- Mathematics, Computer Science
- SODA
- 2019

The first polynomial upper bounds on the number of colors needed in p-centered colorings of graphs drawn from proper minor-closed classes are provided, which answers an open problem posed by Dvoř{a}k. Expand