As everyone knows :P, a graph is a CW-complex of dimension 1. Knowing that, are there any interesting results in graph theory that arise from working with CW-complexes? And more specifically, in algorithms / computability?

  • $\begingroup$ What kind of results are you thinking about? The question is rather broad. Also, consider adding a major tag (those starting with two letters and a dot). $\endgroup$ – Sebastian Goette Nov 9 '15 at 19:07
  • $\begingroup$ I imagine something as "Hey, I'd like to know whether this graph has this X propery....wait! Seeing it as a CW-complex, it's much easier!" $\endgroup$ – Guillermo Mosse Nov 9 '15 at 19:21
  • $\begingroup$ So I guess things like the hom-complexes used to study colorability are not what you are interested in? You only want to consider the graphs themselves as topological spaces? $\endgroup$ – Patrik Nov 9 '15 at 19:27
  • $\begingroup$ That sounds like something I'd be interested to read about, thanks. Are you talking about this? (link) ? Do you have any paper for me? Anyway, although what you say seems cool, yeah, my main interest is to see the graph as a complex and see what I can obtain from that $\endgroup$ – Guillermo Mosse Nov 9 '15 at 19:33
  • $\begingroup$ Configuration spaces in graphs are related to motion-planning problems and they are natural CW-complexes associated to graphs. $\endgroup$ – Ryan Budney Nov 9 '15 at 19:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.