Every proper minor-closed graph class admits an optimal (1+o(1)) log n bit adjacency labeling scheme.
Quickly excluding a non-planar graph
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
citation-role summary
background 2
method 1
citation-polarity summary
verdicts
UNVERDICTED 5representative citing papers
The size of minimal excluded minors for a surface of genus g is O(g^{8+ε}).
In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.
citing papers explorer
-
Adjacency labelling for proper minor-closed graph classes
Every proper minor-closed graph class admits an optimal (1+o(1)) log n bit adjacency labeling scheme.
-
A polynomial bound for the minimal excluded minors for a surface
The size of minimal excluded minors for a surface of genus g is O(g^{8+ε}).
-
A coarse Menger's Theorem for planar and bounded genus graphs
In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.
-
Colorful Minors
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
-
An Overview of Universal Obstructions for Graph Parameters
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.