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$ – Timothy Sun Aug 18 '11 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.