# VLSI circuit embeddings

In the following paper by Valiant

http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf

He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 with size $n$ can be embedded in the grid $Gd_{3n,3n}$ (the square grid of size $9n^{2})$. My question is has he made some kind of assumptions on these graphs as just because the number of edges (the size) is $n$ what's to stop us having a loads of isolated vertices which are not able to be embedded? He doesn't seem to mention that the graph is connected or that it contains no isolated vertices.

This is entirely analaogous (or perhaps complementary) to the situation with the usual definition of a function taught to undergraduates. We say that a function from $A$ to $B$ is a set of pairs $(a, b)$ where each $a \in A$ occurs in the left place exactly once, but this definition means that a function from $A$ to $B$ does not tell you $B$. Sometimes you care about $B$, so you could define a function from $A$ to $B$ to be a triple $(f, A, B)$ with $f$ a set of pairs as above, but this is rarely done.