# Planar graph

• Jul 24th 2010, 03:45 AM
usagi_killer
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:

http://img245.imageshack.us/img245/3914/planargraph.jpg

... 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~
• Jul 24th 2010, 03:48 AM
Ackbeet
That's probably a matter of definition: do you allow complex faces that can be further subdivided into constituent faces? My guess is no.
• Jul 24th 2010, 04:09 AM
usagi_killer
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?
• Jul 24th 2010, 04:24 AM
Plato
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.
• Jul 24th 2010, 04:56 AM
usagi_killer
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
• Jul 24th 2010, 04:58 AM
Ackbeet
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.
• Jul 24th 2010, 05:05 AM
usagi_killer
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!
• Jul 24th 2010, 07:21 AM
Ackbeet
You're very welcome.