Suggest a Book

# Orienting a Planar Graph

Level: unknown

posted Jun 05 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...
• Exercise (easy) : Prove that the edges of any planar graph $G$ can be oriented to obtain a directed graph $D$ so that the maximum out-degree in $D$ is bounded by five.

• Exercise (relatively hard) : Prove that the edges of any planar graph $G$ can be oriented to obtain a directed graph $D$ so that the maximum out-degree in $D$ is bounded by three.

delete retag edit

## Stats

Posted: Jun 05 '12

Seen: 63 times

Last updated: Jun 07 '12