REVIEW 1 cited by
New representation results for planar graphs
Not yet reviewed by Pith; the record is open.
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
read the original abstract
A universal representation theorem is derived that shows any graph is the intersection graph of one chordal graph, a number of co-bipartite graphs, and one unit interval graph. Central to the the result is the notion of the clique cover width which is a generalization of the bandwidth parameter. Specifically, we show that any planar graph is the intersection graph of one chordal graph, four co-bipartite graphs, and one unit interval graph. Equivalently, any planar graph is the intersection graph of a chordal graph and a graph that has {clique cover width} of at most seven. We further describe the extensions of the results to graphs drawn on surfaces and graphs excluding a minor of crossing number of at most one.
Forward citations
Cited by 1 Pith paper
-
Short Paths in the Planar Graph Product Structure Theorem
Every n-vertex planar graph is contained in H ⊠ P ⊠ K_c for some planar H of treewidth 3 and a path P of length O((tw(G)+1)^(1-ε) n^ε).
Discussion (0). Continue with ORCID to comment.