2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

This was meant to be a comment but it was a bit too long, sorry!

There is a well known algorithm to draw a planar graph, namely Tutte's drawing algorithm. The input graph is assumed to be 3-connected and planar. The idea of the algorithm is to fix the position of vertices of a face in convex position and from those coordinates deduce the positions for the rest of the vertices. The resulting drawing being a planar drawing of the input graph. Perhaps you can find more about this at [1].

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.

Are you thinking about drawings subject to more specific constraints?

$\endgroup$
  • $\begingroup$ Thanks so much! And yes, I was thinking for example of constraining multiple nodes to let's say any position along a specific row of the grid. So nodes A and B could have any x-coordinate in the grid but the same fixed y-coordinate. $\endgroup$ – Jack Lynch Aug 3 '17 at 17:36
  • $\begingroup$ I don't see how this answers the question. Do any of these algorithms allow one to constrain the locations of some nodes? Please don't use the answer box to post comments, ask clarification questions, or anything that doesn't directly answer the question. $\endgroup$ – D.W. Aug 3 '17 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.