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...
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for Planar graph check Date
How does one graph a vector? Nov 18, 2015
Planar angle between two vectors Sep 12, 2015
Basic Graph Theory Question Oct 23, 2014
Graphs for linear equations/inequalities Jul 21, 2014
Graphing a plane Sep 8, 2013