Find a set of intervals such that the graph below is the interval graph for your set.
Let C6 be a graph with six vertices, connected into a single cycle.
Draw the planar dual of the graph shown below.
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?
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.