Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Planar graph check

  1. Aug 21, 2012 #1
    I have this graph
    Drawing1 (2).jpg

    now i should check if this graph can be planar.

    v - number of vertices
    e - number of edges
    f - number of faces

    to be planar it should hold v - e + f = 2 from here f = 2 - v + e = 2 - 9 + 15 = 8
    so f = 8 now my question is how to easily count faces (regions bounded by edges, including the outer, infinitely large region) of the graph??
  2. jcsd
  3. Aug 21, 2012 #2


    Staff: Mentor

    couldnt you start with point a and then compile a list of connections that come back to a



    and continue to point b, c, d ... making sure not to count the same loop again

    as an example b-e-a is the same as a-b-e
  4. Aug 21, 2012 #3


    User Avatar
    Science Advisor

    How about arguing that your graph contains neither a K3,3 nor a K5

    as a subgraph? it seems there are not that many cases to consider...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook