A graph is made of nodes and edges. Graphs can be used to model many different situations. For instance, modern supercomputers are made of hundreds of thousands computing nodes: they are massively parallel systems. These nodes are connected according to the interconnection network of the system: nodes are processors and edges are links between them. Routing problems in this context are critical issues as they condition data communication efficiency and reliability. What would be the point of having numerous processors if they are not able to communicate with each other efficiently?