3
$\begingroup$

I'm reading the following paper on universality considerations in VLSI circuits

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

In Theorem 2 On the second page it states there exists constants $c_{1},c_{2}$ such that $c_{1}n^{2}\leq X\ll(n) \leq c_{2}n^{2}$

In the construction it states $9n^{2}$ suffices. Can anybody explain how the explicit construction works? It states that the first $I$ vertices can be embedded in a grid of size $3I \times 3I$ and they use figure $2$ to explain it. However the explanation is brief and i can't seem to make sense of the construction i was wondering whether someone could provide some useful insights?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Here are some more details. We will prove the following stronger claim.

Theorem. Let $G$ be a planar graph with $n$ vertices and maximum degree 4. For every planar embedding $\Gamma$ of $G$, there is a rectilinear embedding $\Gamma'$ of $G$ such that $\Gamma$ and $\Gamma'$ have the same outer face, and $\Gamma'$ is contained in a $3n \times 3n$ grid.

Proof. We proceed by induction on $n$. Clearly, the claim holds for $n=1$. For the inductive step let $\Gamma$ be an arbitrary planar embedding of $G$, and let $v$ be a vertex on the outerface of $\Gamma$. Let $\Gamma_0$ be the embedding obtained from $\Gamma$ by deleting $v$. By induction, there is a rectilinear embedding $\Gamma_0'$ of $G -v$, such that $\Gamma_0$ and $\Gamma_0'$ have the same outerface, and $\Gamma_0'$ is contained in a $3(n-1) \times 3(n-1)$ grid. It remains to show that we can extend $\Gamma_0'$ to a rectilinear embedding of $G$, while only increasing the grid size by $3$. This is shown in Figure $2$ of the paper.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry but i think there is a mistake in your theorem. In the original paper isn't $n$ the number of edges and NOT the number of vertices? I say this because it states in the first few lines under Definitions the size $|G|$ of $G$ is the cardinality of $E(G)$? Then in the definition of $X\ll(n)$ is uses $|G|=n$. $\endgroup$
    – Pavan Sangha
    Commented Oct 15, 2015 at 10:14
  • $\begingroup$ Is this a mistake on their part? Otherwise i could flood a graph with $n$ edges with loads of isolated vertices which couldn't fit into a grid? $\endgroup$
    – Pavan Sangha
    Commented Oct 15, 2015 at 10:16
  • $\begingroup$ It looks like it isn't a mistake however because in the text before the definition of $X \sim (n)$ they mention 'size' $n$. $\endgroup$
    – Pavan Sangha
    Commented Oct 15, 2015 at 10:22
  • $\begingroup$ Your post proves the theorem to show that such an embedding is possible but can it also provide the basis of an algorithm constructing such an embedding? $\endgroup$
    – Pavan Sangha
    Commented Jun 20, 2016 at 14:40

You must log in to answer this question.

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