Pith. sign in

REVIEW 2 cited by

Notes on Graph Product Structure Theory

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2001.08860 v2 pith:I2KCDVZL submitted 2020-01-24 math.CO cs.CGcs.DM

Zdeněk Dvořák , Tony Huynh , Gwenaël Joret , Chun-Hung Liu , David R. Wood This is my paper · ORCID
classification math.COcs.CGcs.DM
keywords graphclassesproductdefinedstructureboundedexplorepolynomial
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

It was recently proved that every planar graph is a subgraph of the strong product of a path and a graph with bounded treewidth. This paper surveys generalisations of this result for graphs on surfaces, minor-closed classes, various non-minor-closed classes, and graph classes with polynomial growth. We then explore how graph product structure might be applicable to more broadly defined graph classes. In particular, we characterise when a graph class defined by a cartesian or strong product has bounded or polynomial expansion. We then explore graph product structure theorems for various geometrically defined graph classes, and present several open problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Row pathwidth of complete binary trees

    math.CO 2026-08 accept novelty 8.0 of 10

    The row pathwidth of the height-h complete binary tree is at least floor((h+1)/16), so it grows linearly with h and matches the general upper bound up to constants.

  2. Shorter Labeling Schemes for Planar Graphs

    cs.DS 2019-08 accept novelty 7.0 of 10

    Every n-vertex planar graph admits an adjacency labeling scheme with labels of length (4/3+o(1)) log n, improving the previous (2+o(1)) log n bound.

Pith tools