0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Jun 8 '16 at 11:25
  • $\begingroup$ 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. $\endgroup$ – Adam Minas Jun 8 '16 at 11:35
  • $\begingroup$ If it were me, I'd check for other ways to decide planarity. $\endgroup$ – Raphael Jun 8 '16 at 11:41
  • 2
    $\begingroup$ Isn't it just the "cycle basis" linked from the lead paragraph of the Wikipedia article? $\endgroup$ – David Richerby Jun 8 '16 at 11:47
  • 1
    $\begingroup$ I agree with David. You find the basis using linear algebra. $\endgroup$ – Yuval Filmus Jun 8 '16 at 13: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.