H.1 Graphs

A graph is a collection of nodes and edges, i.e., G = ( V, E). See figure H.1. Sometimes, another term for a node is vertex, and this chapter uses the two terms interchangeably. We use G for graph, V for vertex (or node), and E for edge. Typically in motion planning, a node represents a salient location, and an edge connects two nodes that correspond to locations that have an important relationship. This relationship could be that the nodes are mutually accessible from each other, two nodes are within line of sight of each other, two pixels are next to each other in a grid, etc. This relationship does not have to be mutual: if the robot can traverse from nodes V ₁ to V ₂, but not from V ₂ to V ₁, we say that the edge E ₁₂ connecting V ₁ and V ₂ is directed. Such a collection of nodes and edges is called a directed graph. If the robot can travel from V ₁ to V ₂ and vice versa, then we connect V ₁ and V ₂ with two directed edges E ₁₂ and E ₂₁. If for each vertex V _i that is connected to V _j, both E _ij and E _ji exist, then instead of connecting V _i and V _j