Drawing planar graphs
Donald R. Woods · 1981
Given a planar graph, we wish to draw it in the plane so that no edges cross. We might be given a particular planarisation (a specification giving the faces of the desired drawing) instead of merely the graph, but this is not required. Given a planarisation and a choice of outermost face, all drawings are in a sense equivalent; indeed, when the drawing is performed on the surface of a sphere instead of on the plane, even the choice of outermost face is irrelevant. To make the problem meaningful, we must introduce further constraints. Two general forms of constraints are: (1) absolute restrictions on the details of the drawing, that is, disallowing or requiring certain features, and (2) weighted restrictions, that is, additional objectives to be met to whatever extent is possible. We first examine the general problem, and look at various constraints that have been found to yield useful drawings in some applications. We then examine in more detail one particular set of constraints, developing a fast algorithm for producing drawings meeting those constraints, and proving some theorems relating to the overall complexity of the problem. Finally, we look at what results are known regarding other variations on the general problem.