5
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ @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. $\endgroup$
    – Oleksandr Bondarenko
    Mar 28, 2011 at 10:23
  • $\begingroup$ @oleksandr, question updated. Also, I explicitly mention that the graph can be embedded. $\endgroup$
    – Graviton
    Mar 28, 2011 at 10:27
  • $\begingroup$ @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? $\endgroup$
    – Oleksandr Bondarenko
    Mar 28, 2011 at 10:41
  • $\begingroup$ @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, $\endgroup$
    – Graviton
    Mar 28, 2011 at 11:15
  • 3
    $\begingroup$ @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 scholar.google.com/…). $\endgroup$
    – Oleksandr Bondarenko
    Mar 28, 2011 at 11:49

2 Answers 2

Reset to default
11
$\begingroup$

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," Graph Drawing, 283--294, 2004.
Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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