2
$\begingroup$

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to intersect except at end points. I'm aware that 4-planar graphs admit orthogonal embeddings in 2-dimensions

In particular i'm interested in two measures the maximum edge length of an embedding and the sum of all edge lengths. That is given a $4$-planar graph $G=(V,E)$, let $\mathrm{length}(e)$ for $e \in E$ denote the length of the edge in an orthogonal embedding of $G$. I'm interested in known results on

1.$\mathrm{max} \{\mathrm{length}(e): e \in E\}$.

2.$ \sum_{e \in E} \mathrm{length}(e)$

In particular i'm interested in how these two measures grow as functions of $|V|$ in the best embeddings (best meaning as small as possible). For example i have seen for three dimensional orthogonal embeddings the maximum edge length often grows as a function of order $\sqrt{|V|}$. Is there anything that has been done in 2-dimensions?

I appreciate any help.

$\endgroup$
2
$\begingroup$

This is not a direct answer, but in the context of "orthogonal compaction"—after planarization, embedding, and bend minimization—achieving minimum total edge length, or minimizing the longest edge, are both NP-hard,1 and inapproximable within a polynomial factor of optimality.2

1 M. Patrignani. On the complexity of orthogonal compaction. Computational Geometry 19(1):47–67, 2001. (Elsevier link.)

2 Joseph, Michael, J. Bannister, David Eppstein, and A. Simons. "Inapproximability of orthogonal compaction." (2012). (arXiv abstract.)

$\endgroup$

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.