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)?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ intensive purposes $\to$ intents and purposes $\endgroup$
    – Anthony Quas
    Commented Jun 17, 2015 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
    Commented Jun 17, 2015 at 15:56
  • $\begingroup$ Yes that's what i thought transform each co-ordinate $(x,y)$ to $(4x,4y)$. $\endgroup$
    – Lfmoamse
    Commented Jun 17, 2015 at 20:27

2 Answers 2

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 18, 2015 at 9:22
  • $\begingroup$ Yes i'm looking for line segments being parallel to the axis. $\endgroup$
    – Lfmoamse
    Commented Jun 19, 2015 at 7:58
  • $\begingroup$ @L You can check Section 1.3 of this recent paper: arxiv.org/pdf/1506.04423.pdf $\endgroup$
    – domotorp
    Commented Jun 20, 2015 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.).

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .