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
    Hi
    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??
    thanks
     
  2. jcsd
  3. Aug 21, 2012 #2

    jedishrfu

    Staff: Mentor

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

    a-b-e

    a-b-f-i

    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

    Bacle2

    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...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Planar graph check
  1. Checking Primes (Replies: 1)

  2. Coloring graphs (Replies: 1)

  3. Groups and graphs (Replies: 1)

  4. Graph theory (Replies: 1)

  5. Graphing a plane (Replies: 2)

Loading...