Proper orientations of planar bipartite graphs (Q1684937)

An orientation of a graph is proper if any two adjacent vertices have different indegrees. The proper orientation number of a graph is the minimum of the maximum indegrees taken over all its proper orientations. It is an open question whether the class of planar bipartite graphs has a bounded orientation number. The authors begin with a new and useful result that yields a polynomial-time algorithm to properly orient a connected bipartite graph, and to do so when controlling only the orientation of a spanning tree and the edges incident with one of its leaves. This algorithm produces a proper orientation with indegree at most 6 for a 3-connected planar bipartite graph, and with indegree at most 4 for a tree. (The later bound was known but the proof was not constructive.) By modifying their general construction, they show the proper orientation number of a 3-connected planar bipartite graph is at most 5.