2
$\begingroup$

The problem is that of spatially (with or without a fixed spatial dimension) organizing a graph so that each node becomes a cell in a grid, and each edge becomes a line, such that the total combined length of all lines (edges) is the minimal.

I want to know if that problem has a name, and how complex it is. I also would like to know if this problem is easier if done incrementally (i.e., starting with an empty graph and adding/removing nodes as to maintain that property).

$\endgroup$
  • $\begingroup$ I recommend that you merge your two accounts, using the method described here: cs.stackexchange.com/help/merging-accounts. Having multiple accounts is not strictly prohibited, if you're very careful about how you use them to make sure you follow the guidelines established for this, but as soon as there is any interaction between the accounts (e.g., both accounts showing up on the same post), it becomes strictly prohibited. $\endgroup$ – D.W. Dec 20 '15 at 22:11
3
$\begingroup$

This is a version of graph drawing, restricted to vertices being on a grid, but allowing more than two dimensions. The one-dimensional case is an example of a graph layout problem, known as Minimum Linear Arrangement. In all of these problems, one is interested in minimizing some metric of the resulting diagram, which could be the number of edge crossings or, in your case, the total length of the edges.

These kinds of problem are very often NP-hard, even in the one-dimensional case: in particular Minimum Linear Arrangement, the 1D version of your problem, is NP-hard. There's a survey of graph layout problems by Díaz, Petit and Serna (ACM Surveys, 34:313–356, 2002; .ps.gz).

$\endgroup$
  • $\begingroup$ Hi, I'm OP (I'm not sure why I can't login on the other account). Here's for me hoping it would be an easy problem. Do you by chance know if there is an easy solution for the problem of incrementally building such a graph, for the case of an 1D grid, where each node is either a terminal node with one edge, or a ternary node with 3 edges? $\endgroup$ – MaiaVictor Dec 20 '15 at 20:46
  • $\begingroup$ It's possible that problems in higher dimensions are easier (for example, it's not quite trivial to check if a graph is planar, i.e., embeddable in 2D space without edges crossing, but every graph can be embedded trivially in 3D space without crossings). The restricted 2D case you describe in your comment could also be easier. $\endgroup$ – David Richerby Dec 20 '15 at 21:27
  • $\begingroup$ I see, thank you. The actual use case for which I want this is to keep nodes close together in space for a graph-reduction algorithm, so that I make better use of the processor caches. I'll investigate the subject further. Thanks! $\endgroup$ – MaiaVictor Dec 20 '15 at 21:42

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.