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?
Improve this question
$\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$
    – Louis Deaett
    Commented Sep 24, 2015 at 12:18
  • 1
    $\begingroup$ Which paper are you reading? $\endgroup$
    – j.c.
    Commented 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
    Commented 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$
    – Pavan Sangha
    Commented Sep 24, 2015 at 14:51
  • $\begingroup$ Is there a mistake in the paper? $\endgroup$
    – Pavan Sangha
    Commented Sep 24, 2015 at 14:54

3 Answers 3

Reset to default
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)$.

Improve this answer
$\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)$.

Improve this answer
$\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.

Improve this answer
$\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$
    – Pavan Sangha
    Commented 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
    Commented 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$
    – Pavan Sangha
    Commented 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
    Commented Sep 24, 2015 at 15:58
  • $\begingroup$ Regarding the $O(|V|)$ should it be $O(|V|^{2})$? $\endgroup$
    – Pavan Sangha
    Commented Sep 24, 2015 at 16:11

You must log in to answer this question.

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