A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are obstructions that prevent the graph from being genus $g$. Is there any result on the size of the list? Is it linear in $g$?
2 Answers
$\begingroup$
$\endgroup$
2
No, it is not linear in the genus; it is at least exponential in $g$. See for example this answer by David Eppstein.
answered Jan 13, 2016 at 21:39
-
$\begingroup$ i dont see a reference for 'at least'. $\endgroup$– user76479Jan 14, 2016 at 14:21
-
1$\begingroup$ As Eppstein mentions, if you take a graph which consists of exactly $g+1$ blocks, each of which is a $K_5$ or a $K_{3,3}$, then this will be an excluded minor for embedding in a surface of genus $g$. There are obviously at least $2^{g+1}$ such graphs. $\endgroup$ Jan 14, 2016 at 15:43
$\begingroup$
$\endgroup$
It seems that this paper by Djidjev and Reif establishes an upper bound of $\exp(O(g)!)$ for the number of minimal forbidden minors.
Djidjev, Hristo, and John Reif. "An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs." Proceedings of the twenty-third annual ACM symposium on Theory of computing. ACM, 1991.
