A *planar graph* is a graph that can be drawn on the plane in such a way that edges intersect only at their end points. Figure 4.6 shows a planar graph. In *geometric graphs*, each node is aware of its position and those of its neighbors, and therefore angles toward them. Examples of planar and geometric graphs include street maps, or rooms on the same floor in a building. Planar geometric graphs divide graph into faces. In the example in Figure 4.6, face *F*_{1} is polygon *SABC* and face *F*_{2} is polygon *BEFGHC*. Kranakis *et al*. (1999) described the first localized memoryless routing algorithm for planar geometric graphs, which guarantees delivery whenever the source and destination are connected.

The face routing in Bose *et al*. (1999) is an improvement on the routing algorithm in Kranakis *et al*. (1999). The main idea of the face routing (Bose *et al*., 1999) is to advance (toward destination *D*) intersections of faces with a straight line segment that connects the last intersection *X* (initially it is the source *S*) and the destination *D*. A packet is routed along the interiors of the faces until an edge on the route intersects *XD* between *X* and *D*. In Figure 4.6, the line intersects the planar graph with faces *F*_{1}, *F*_{2}, …, *F*_{7}. The boundary of any face can be traversed by applying the right-hand rule (counterclockwise traversal) or the left-hand rule (clockwise traversal). In the right-hand rule, the face is traversed ...

Start Free Trial

No credit card required