In honor of the recently passed Graph Drawing deadline....
Suppose we place all the vertices of a graph on the spine of a book, and partition the edge set into sets such that each set can be drawn on a single page without crossings. The page number of a graph is the minimum number of pages required to draw a graph in this way. Clearly an outerplanar graph has page number 1.
A well known result by Yannakakis states that any planar graph can be drawn with page number 4, and this is necessary. A very interesting related result by Lenwood Heath in SODA 1991 states that the edges of a planar graph can be partitioned into two parts, each inducing an outer planar graph.
It is NP-hard to determine whether a given planar graph has page number 2 or not.
No comments:
Post a Comment