Lately, something I've been interested in is finding the set of forbidden minors for the apex graphs. One thing I tried to do was to look at the graphs which were known, and try to find a pattern in the planar subgraphs that result from deleting two vertices. However, when trying this on the Petersen family, what came out of it didn't look that nice. Luckily, the $Y-\Delta$ transformations give a simple characterization of the Petersen family as the equivalence class containing, say, $K_6$ under $Y-\Delta$ transformations.

After some preliminary googling, I came across a blog post by David Eppstein in which he lists a bunch of forbidden minors for apex graphs by carefully attaching copies of $K_5$ and $K_{3,3}$ together. I was hoping to find some more not listed there (besides the trivial disjoint unions of $K_5$ and $K_{3,3}$) using $Y-\Delta$ transformations, but found that sometimes the resulting graphs are apex. Is there any characterization (or just weak conditions) of when apexness is preserved?

  • $\begingroup$ I tried generating the $Y\Delta Y$ equivalence class for the first drawn graph in the blog post, but unfortunately, there are at least a thousand graphs in this class. I restricted the search to non-apex graphs, and already got 15 non-isomorphic forbidden minors. In my mind, a computational approach to this problem is hopeless. :/ $\endgroup$ Aug 18, 2011 at 7:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.