# Planar Embedding with Some Nodes Constrained

I've read about basic planar-graph embedding and about embedding a planar graph onto a set of fixed points, but I was wondering how one might constrain the locations of some nodes—perhaps to a set of points—while allowing others complete freedom.

Is this achievable with a current popular algorithm, or with minor modification thereto? I guess the nature of the problem would lend itself better to grid-based embeddings, right?

I'm entirely new to graph theory, so it's possible the answer is obvious to those familiar with the field. I didn't see anything about it while searching.

With respect to grids, there are a couple of well known algorithms for drawing planar 3-connected graphs. One is Schnyder's algorithm (through the a Schnyder wood decomposition of the edges), and the canonical ordering algorithm (through a partition of the vertices of the graph). Both of these algorithms run in $O(n)$ time and produce drawings in an $O(n)\times O(n)$grid, where $n$ is the number of vertices of the input graph. At [2] you may find an overview of these two algorithms for the case of planar triangulations. You could even go to references [4] and [9] cited there for the original papers. It is worth noting that these algorithms have been generalized to work on 3-connected planar graphs as stated above.