CS 163, Spring 2012, Homework 8, due Thursday, June 8

1. Find a set of intervals such that the graph below is the interval graph for your set.

   

2. Let C₆ be a graph with six vertices, connected into a single cycle.

   1. How many colors are needed in an optimal coloring of C₆?
   2. Find an ordering of the vertices of C₆ for which the greedy coloring uses more than the optimal number of colors. What is the coloring that the greedy algorithm finds in this case?

3. Draw the planar dual of the graph shown below.

   

4. The proof given in class for Euler's formula V − E + F = 2 assumes that the given planar graph is connected (because otherwise it would not have any spanning trees). Is the formula still valid for planar graphs that are not connected? Why or why not?

5. What is the worst-case running time of the Bellman–Ford algorithm when its input is a planar graph? You should express your answer in O-notation as a function only of the number n of vertices; do not include the number m of edges in your answer.