<p>Check TULIP - <a href="http://tulip.labri.fr/TulipDrupal/" rel="nofollow">http://tulip.labri.fr/TulipDrupal/</a>, it might work well for you</p>

CC BY-SA 2.5
2011-03-28T16:03:37.790Z
2011-03-28T16:03:37.790Z
Tatiana Starikovskaya
<p>There is considerable work on the problem of finding planar embeddings with specified edge lengths. Survey and some results can be found in $[1]$.</p>

<ol>
<li>Cabello, S. and Demaine, E.D. and Rote, G., "<a href="http://www.springerlink.com/index/37L47FTFJ2MVX2H7.pdf" rel="nofollow">Planar embeddings of graphs with specified edge lengths</a>," Graph Drawing, 283--294, 2004.</li>
</ol>

CC BY-SA 2.5
2011-03-28T15:48:56.010Z
2011-03-28T15:48:56.010Z
Oleksandr Bondarenko
<p>Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not. </p>

<p>Further assume that this is a graph that can be embedded on a 2D plane, what is the algorithm that can create a "nice" drawing with no edge intersection?</p>

<p>Obviously there are many ways the graph can be drawn, and the definition of nice is a bit fuzzy (for practical purpose I would define it as something that is pleasing to the human eyes), but I would only need a good enough algorithm for this.</p>

<p>Note there could be many graphs with its embedding and I frankly don't care the algorithm gives me which, as long as it is pleasant looking enough and it has all the above constraint satisfied. </p>

<p>The motivation for this question is this: imagine that you have to design a circuit layout, the path that connects between two electronic components is $E$, and the vertex of each component is $V$, as a part of your engineering design you know that the distance between each component is pre-specified. As a designer, you would have to arrange the components on the board so that it looks nice. How can you design the circuit layout?</p>

CC BY-SA 2.5
2011-03-28T10:23:20.230Z
@Graviton:The question is essentially not about embeddings but about drawings. So it's desirable to change the title of your question. Further, I guess, it should be specified whether planar embedding of graph is given and if it's not then whether the problem of finding planar embeddings of the considered class is in P.
Oleksandr Bondarenko
CC BY-SA 2.5
2011-03-28T10:27:56.800Z
@oleksandr, question updated. Also, I explicitly mention that the graph *can* be embedded.
Graviton
CC BY-SA 2.5
2011-03-28T10:41:35.603Z
@Graviton: As I understood you have possibly one graph with its embedding and you care only about aesthetic drawing of only this one, doesn't you?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-03-28T11:15:38.117Z
@Oleksandr, nope. There could be many graphs with its embedding and I frankly don't care the algorithm gives me which, as long as it is pleasant looking enough,
Graviton
CC BY-SA 2.5
2011-03-28T11:49:45.677Z
@Graviton: I mean if you consider arbitrary graphs then how you could find desired drawing with the given edge lengths if even for restricted classes of graphs finding Planar Embedding with Specified Edge Lengths is NP-hard (see http://scholar.google.com/scholar?hl=en&q=%22Planar+embeddings+of+graphs+with+specified+edge+lengths%22&btnG=Search&as_sdt=1%2C5&as_ylo=&as_vis=0).
Oleksandr Bondarenko
CC BY-SA 2.5
2011-03-28T15:31:39.487Z
@Oleksandr, why don't you put this as an answer? I mean for the paper. And I am not quite sure whether your comment has a question.
Graviton
<graph-algorithms><cg.comp-geom><planar-graphs><embeddings>
Graph planar drawing, with each edge's length is known
Graviton
# Graph planar drawing, with each edge's length is known

(Asked by: username_0 on 2011-03-28)

Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not.

Further assume that this is a graph that can be embedded on a 2D plane, what is the algorithm that can create a "nice" drawing with no edge intersection?

Obviously there are many ways the graph can be drawn, and the definition of nice is a bit fuzzy (for practical purpose I would define it as something that is pleasing to the human eyes), but I would only need a good enough algorithm for this.

Note there could be many graphs with its embedding and I frankly don't care the algorithm gives me which, as long as it is pleasant looking enough and it has all the above constraint satisfied.

The motivation for this question is this: imagine that you have to design a circuit layout, the path that connects between two electronic components is $E$, and the vertex of each component is $V$, as a part of your engineering design you know that the distance between each component is pre-specified. As a designer, you would have to arrange the components on the board so that it looks nice. How can you design the circuit layout?

**Tags:** graph-algorithms, cg.comp-geom, planar-graphs, embeddings
> **Comments:**
> **username_1**: @Graviton:The question is essentially not about embeddings but about drawings. So it's desirable to change the title of your question. Further, I guess, it should be specified whether planar embedding of graph is given and if it's not then whether the problem of finding planar embeddings of the considered class is in P.  
> **username_0**: @oleksandr, question updated. Also, I explicitly mention that the graph *can* be embedded.  
> **username_1**: @Graviton: As I understood you have possibly one graph with its embedding and you care only about aesthetic drawing of only this one, doesn't you?  
> **username_0**: @Oleksandr, nope. There could be many graphs with its embedding and I frankly don't care the algorithm gives me which, as long as it is pleasant looking enough,  
> **username_1**: @Graviton: I mean if you consider arbitrary graphs then how you could find desired drawing with the given edge lengths if even for restricted classes of graphs finding Planar Embedding with Specified Edge Lengths is NP-hard (see http://scholar.google.com/scholar?hl=en&q=%22Planar+embeddings+of+graphs+with+specified+edge+lengths%22&btnG=Search&as_sdt=1%2C5&as_ylo=&as_vis=0).  
> **username_0**: @Oleksandr, why don't you put this as an answer? I mean for the paper. And I am not quite sure whether your comment has a question.  

---

## 2 answers

### Answer by username_1 on 2011-03-28. Score: 11 | Accepted answer

There is considerable work on the problem of finding planar embeddings with specified edge lengths. Survey and some results can be found in $[1]$.

1. Cabello, S. and Demaine, E.D. and Rote, G., "[Planar embeddings of graphs with specified edge lengths](http://www.springerlink.com/index/37L47FTFJ2MVX2H7.pdf)," Graph Drawing, 283--294, 2004.


---

### Answer by username_2 on 2011-03-28. Score: 0

Check TULIP - <http://tulip.labri.fr/TulipDrupal/>, it might work well for you


---

