Suggest a Book

# Recognizing series-parallel graphs in linear time

Level: unknown

posted Jun 07 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

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.

delete retag edit

Are we allowed to assume for the last part that we can identify the node with least degree in O(1) time?

(Jul 21 '12)edit

## Stats

Posted: Jun 07 '12

Seen: 29 times

Last updated: Jun 07 '12