9
$\begingroup$

I've seen the following lemma in a paper. The result is by 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 have two questions.

  1. Although not explicitly stated i assume the embedding is planar too?
  2. Is there anything regarding the shape of the area that the graph is embedded into other than the fact it's area is $O(|V|)$ ? More specifically can we for example ensure that the graph can be embedded in a $|V|\times |V|$ grid?
$\endgroup$
5
  • 4
    $\begingroup$ By some sort of continuity argument, one can always take the points of a planar embedding to be in $\mathbb Q \times \mathbb Q$, and then scale everything up so that the coordinates will all be integers. So the $O(|V|)$ bound would really seem to be the essential aspect of the result. $\endgroup$ Sep 24, 2015 at 12:18
  • 1
    $\begingroup$ Which paper are you reading? $\endgroup$
    – j.c.
    Sep 24, 2015 at 14:16
  • 3
    $\begingroup$ @j.c. It is likely Universality Considerations in VLSI Circuits computer.org/csdl/trans/tc/1981/02/06312176.pdf $\endgroup$
    – Tony Huynh
    Sep 24, 2015 at 14:27
  • 3
    $\begingroup$ Hi guys, just make sure i haven't misstated Valiant's result here is the paper where i found it stated ac.els-cdn.com/0012365X9090358O/… it's on page 4 of the document under lemma 2.1. And yes the paper i'm referring to is the one mentioned above. $\endgroup$ Sep 24, 2015 at 14:51
  • $\begingroup$ Is there a mistake in the paper? $\endgroup$ Sep 24, 2015 at 14:54

3 Answers 3

9
$\begingroup$

As far as I understand, I think you have misstated Valiant's result.

Regarding $1$, yes the embedding is assumed to be planar, with the edges constrained to follow the 'edges' of the grid. This is called a rectilinear embedding. Note that only graphs with maximum degree 4 have rectilinear embeddings, hence the degree restriction. Secondly, the area of the embedding is defined to be the area of the smallest box bounding the embedding. Thus, the $O(V)$ area condition is quite strong (in particular, the length or width is $O(\sqrt V)$). Finally, Valiant's result is actually for trees with maximum degree $4$. He showed that the $O(V)$ area condition is false in general; there are planar graphs with maximum degree 4 that require bounding area $O(V^2)$.

Edit. For the benefit of others who have not followed the chat, here is a summary. The lemma under consideration is Lemma 2.1 of the paper Unit Disk Graphs by Clark, Colbourn and Johnson. The lemma is due to Valiant, but a typo was was introduced by Clark, Colbourn and Johnson. The $O(|V|)$ should be replaced by $O(|V|^2)$.

$\endgroup$
3
$\begingroup$

There is a huge literature on this topic. Search for "orthogonal graph drawing". The best possible area bound is $O(n^2)$.

$\endgroup$
0
$\begingroup$

Yes. I am not sure what Valiant proved, but as far as I know, the best result on planar graph embedding in the grid is Schnyder's algorithm.. De Fraysseix, Pach, Pollack (1990) show that an $n$-vertex graph can be embedded in a $n-2 \times 2n -4 $ grid.

$\endgroup$
6
  • 2
    $\begingroup$ It looks like this algorithm does not require edges to be orthogonal to the $x$ and $y$ axis (i.e edges are horizontal and vertical lines). $\endgroup$ Sep 24, 2015 at 14:02
  • 2
    $\begingroup$ @CBrosen Note that in rectilinear embeddings the edges are not horizontal and vertical lines; they are a union of horizontal and vertical line segments. $\endgroup$
    – Tony Huynh
    Sep 24, 2015 at 15:00
  • $\begingroup$ @Tony Huynh when you say union you mean a collection of horizontal and vertical lines joined by bends? $\endgroup$ Sep 24, 2015 at 15:32
  • $\begingroup$ Yes, and the bends can only happen at integer points (the vertices are also constrained to lie on integer points). $\endgroup$
    – Tony Huynh
    Sep 24, 2015 at 15:58
  • $\begingroup$ Regarding the $O(|V|)$ should it be $O(|V|^{2})$? $\endgroup$ Sep 24, 2015 at 16:11

Your Answer

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

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