Complexity of edge coloring in planar graphs
Every bridgeless planar cubic graph can be 3-edge-colored in quadratic time, as this task is equivalent to four-coloring a planar graph, which can be done in quadratic time. (See Robertson, Sanders, Seymour and Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDIT: As Mathieu points out, cubic graphs with bridges are never 3-edge colourable.