VLSI circuit embeddings

Question

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.

Answer 1

The unstated assumption is that there are no isolated vertices.

It's very easy to make this sort of formal error in a context where you're thinking of a graph as a set of edges. We normally define graphs to be a pair of a vertex set and an edge set because sometimes we do care about isolated vertices, but there are also times when we don't, and in those cases it is more convenient to use a different definition, although people don't often give it explicitly.

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.