Let $G(V,E)$ be a simple undirected graph with $|V| = n$ and $|E| = m$. Let the treewidth of $G$ be at most $k$.
Derive a tight upper bound of $m$ in terms of $n$ and $k$. Show that this upper bound is achieved by chordal graphs.
Prove that $G$ has at least one vertex of degree at most $k$.
Prove that the treewidth of a series-parallel graph is at most 2.
Design an $O(n)$ time algorithm to decide whether $G$ is a series-parallel graph.
Posted: Jun 07 '12
Seen: 29 times
Last updated: Jun 07 '12
Are we allowed to assume for the last part that we can identify the node with least degree in O(1) time?
aa1062 (Jul 21 '12)edit