8
$\begingroup$

I've recently come across the following lemma.

Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at integer coordinates and its edges are drawn so that they are made up of line segments of the form $x=i$ or $y=j$, for integers $i$ and $j$.

I'd like to first point out that i'm not interested in the size of the area that the graph is embedded in, so we can for all intents and purposes assume it's possible to work in an area of unrestricted size. I'm interested to know (because they haven't explicitly stated) whether any graph in the class mentioned, can be embedded without having any 'bends' in the edges? If it's necessary to allow for 'bends' is there a restriction on the maximum number required? Secondly would i be able to create an embedding where the lengths of all the edges are multiples of $4$ (perhaps by applying some kind stretch to the original graph)?

$\endgroup$
  • 3
    $\begingroup$ intensive purposes $\to$ intents and purposes $\endgroup$ – Anthony Quas Jun 17 '15 at 14:18
  • 2
    $\begingroup$ Surely you can force the lengths of the edges to be multiples of 4 simply by making a grid embedding and then multiplying all the coordinates by 4? $\endgroup$ – Robin Houston Jun 17 '15 at 15:56
  • $\begingroup$ Yes that's what i thought transform each co-ordinate $(x,y)$ to $(4x,4y)$. $\endgroup$ – Lfmoamse Jun 17 '15 at 20:27
7
$\begingroup$

Bends are necessary, we have studied this problem in this paper: http://arxiv.org/abs/1009.1315.

$\endgroup$
  • $\begingroup$ Thanks for the useful info guys! Btw does anybody know if there is a class of graphs which can be embedded with at most one bend? $\endgroup$ – Lfmoamse Jun 18 '15 at 9:22
  • $\begingroup$ Yes i'm looking for line segments being parallel to the axis. $\endgroup$ – Lfmoamse Jun 19 '15 at 7:58
  • $\begingroup$ @L You can check Section 1.3 of this recent paper: arxiv.org/pdf/1506.04423.pdf $\endgroup$ – domotorp Jun 20 '15 at 13:44
12
$\begingroup$

The recent paper below (and its references) may help. They mention that every planar graph with max degree $4$ (except for the octahedron) admits a $2$-bend embedding. Deciding whether a graph can be embedded without bends is NP-hard. The paper details a quadratic algorithm for deciding $1$-bend embeddability.

Bläsius, Thomas, Marcus Krug, Ignaz Rutter, and Dorothea Wagner. "Orthogonal graph drawing with flexibility constraints." Algorithmica 68, no. 4 (2014): 859-885. (Journal link.)

Here is the conference-version abstract:


          Abstract


Added. Here is a (PDF download-link for Thomas Bläsius thesis: Orthogonal Graph Drawing with Flexibility Constraints.).

$\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.