Results 1 to 8 of 8

Math Help - Planar graph

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    Planar graph

    "If a connected, planar graph is drawn on a plane then the plane can be divided into continuous regions called faces. A face is characterised by the cycle that forms its boundary."

    This is what my book says, and then it goes on to illustrate an example by saying this graph:



    ... has 4 faces, namely A, B, C, D (D is the face bounded by the cycle (1,2,3,4,6,1)

    however shouldn't there be at least 6 faces? ie a face bounded by (1,2,5,4,6,1) and (1,2,3,4,5,1)...?

    Many thanks~
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    That's probably a matter of definition: do you allow complex faces that can be further subdivided into constituent faces? My guess is no.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    306
    hmm I am not sure, the book doesn't mention it either, however I thought what you did too, but if they count (1,2,3,4,6,1) as a face, isn't that also made up of constituent faces?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    A planar graph partitions the plane into regions called faces.
    The operative word there is partition, disjoint cells.
    So there are only four faces in that graph.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2009
    Posts
    306
    Hmm but isn't (1,2,3,4,6,1) made up of A+B+C?

    Also for a planar graph, the edges must all be STRAIGHT lines right? Because if they are not... you can bend the lines for a non-planar graph into a planar graph XD
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I'm reminded of the joke that has an engineer, a physicist, and a mathematician fencing off the maximum area with a fixed length of fence. The engineer arranges the fence in a circle and claims to have fenced off the maximum area. The physicist puts the fence in a straight line, and says, "We can assume the fence goes off into infinity, hence I've fenced off half the earth." The mathematician just laughs at the other two. He builds a tiny fence around himself, and says, "I declare myself to be on the outside."

    In a similar fashion, the face D is, I think, "Everything else." If you were to think of this graph as describing a solid, D would be the face consisting of everything else. That's why it's not a composite face.

    I would agree with Plato if the phrase "divided" is a synonym for "partitioned."

    [EDIT]: Edges don't have to be straight lines. Planarity has nothing to do with the straightness of lines. It has everything to do with the particular arrangement of edges and vertices.
    Last edited by Ackbeet; July 24th 2010 at 04:59 AM. Reason: Straight lines.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Apr 2009
    Posts
    306
    Oh yes I get it! Thank you very much Ackbeet and Plato for clearing up the confusion.

    Oh and for the straightness of lines thing, I get it now, I was thinking that if the lines doesn't have to be straight you could somehow bend it so that no lines will every intersect, but after experimenting on a K_{3,3} graph I've convinced myself it can't be done!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    You're very welcome.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Maximal 4-regular Planar Graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 7th 2011, 06:24 PM
  2. Replies: 5
    Last Post: December 22nd 2010, 01:42 AM
  3. is this graph planar?
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: March 3rd 2010, 01:32 PM
  4. isomorphic graph, planar graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 08:13 AM
  5. Planar Graph problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 15th 2007, 12:26 AM

Search Tags


/mathhelpforum @mathhelpforum