Corpus ID: 236772054

# 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}
}
• T. Ueckerdt, David R. Wood, Wendy Yi
• Published 31 July 2021
• Computer Science, Mathematics
• ArXiv
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

#### Figures from this paper

Shallow Minors, Graph Products and Beyond Planar Graphs
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 withExpand
Structural Properties of Graph Products
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 thisExpand

#### 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$ areExpand
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 onExpand
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.742621123790741, "perplexity": 1344.2331313591344}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-49/segments/1637964358469.34/warc/CC-MAIN-20211128043743-20211128073743-00246.warc.gz"}