# Complete set of basic circuits for McLane's Theorem

I was assigned a project in which i had to implement some algorithms concerning graphs. The last one is the one described in the title. I have to make an algorithm that uses McLane's theorem (https://en.wikipedia.org/wiki/Mac_Lane%27s_planarity_criterion) to test whether a graph is planar or not. Now, to do that i have to find something called a 'Complete set of basic circuits', as our professor says. I have searched round a bit, and i could not find this term.

As noted in the book, A complete set of basic circuits S is a set of circles in which: 1) Every circle in S can be expressed as the ring sum of some or all of the circles in S 2) No circle in S can be expressed as the ring sum of any circle that does not belong to S.

Does anyone know how a 'Complete set of basic cricuit' is calculated? Any guidance would be appreciated.

• Welcome to Computer Science! Which resources did you check? What have you tried? Where did you get stuck? We do not want to just do your work for you; we want you to gain understanding. – Raphael Jun 8 '16 at 11:25
• Thanks for your reply! I don't want you to make my work either :D. I checked my book and the slides of my professor. My main problem is that i cant find anything online about a 'Complete set of basic circuits', so maybe a term that will yield more results will help me even more. As of now i think that this set is the set of the minimal cycles, but i think im wrong in that. – Adam Minas Jun 8 '16 at 11:35
• If it were me, I'd check for other ways to decide planarity. – Raphael Jun 8 '16 at 11:41
• Isn't it just the "cycle basis" linked from the lead paragraph of the Wikipedia article? – David Richerby Jun 8 '16 at 11:47
• I agree with David. You find the basis using linear algebra. – Yuval Filmus Jun 8 '16 at 13:10