Algorithms Core 15-750  PROBLEM SET # 4  Spring 1998

DUE: 10:30AM Friday 20 March 1998

1 Hamiltonian Planar Graphs

Let G = (V, E) an undirected graph with no multiple edges or self-loops. A simple cycle in G is call Hamiltonian if includes every vertex of G. Give an O(n) time algorithm which when given G and a Hamiltonian cycle for G determine if the graph G is planar.

A cord is simply an edge which not in the cycle with both of its nodes on the cycle. Thus problem boils down to the following problem: Given a simple cycle of size n and a collection of cords determine if the cords can be embedded with no crossing using either outside face or the inside face.

Hint: This problem is too hard. You can get full credit for an (n^{2}) solution. For those of you who would like to work on an O(n) solution please stop by and we can discuss the problem.

2 Series-Parallel Graphs

A directed acyclic graph G with two distinguished vertices s, t is a series-parallel graph if it is obtained from the following inductive definition:

1. The graph consisting on a single edge from s to t is series-parallel.

2. If G = (V, E, s, t) and G′ = (V′, E′, s′, t′) are series-parallel then

(a) [parallel] the new graph obtained by identifying s with s′ and t with t′ is series-parallel

(b) [series] the new graph obtained by identifying t with s′ is series-parallel

We shall say that a directed graph has an f(n)-separator if the graph has an f(n)-separator when we ignore the direction on the edges and view them as undirected.

Show that every series-parallel graph has a 2-separator. Also give an O(m + n) time algorithm to find this separator.

You may assume that the series-parallel graph is given to you with the parse tree.

3 3-Coloring planar Graphs

Give an O(2^{c\sqrt{n}}) time algorithm to 3-color a planar graph, where c is some fixed constant.

Hint: Use the Planar Separator Theorem.