Orthogonal embeddings and edge lengths

Question

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.

Answer 1

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,¹ and inapproximable within a polynomial factor of optimality.²

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

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