Can every simple graph be embedded on a circuit board?

Question

Here, a circuit board is defined as a pair of planar graphs with vertices identified, i.e. a ordered triple $\langle V,E_1,E_2\rangle$ such that there are planar embeddings $h_1,h_2$ for the planar graphs $\langle V,E_1\rangle$ and $\langle V,E_2\rangle$, respectively, such that $h_1(v)=h_2(v)$ for each $v\in V$. Does every simple graph $\langle V,E\rangle$ admit a decomposition $E=E_1\sqcup E_2$ such that $\langle V,E_1,E_2\rangle$ is a circuit board?

If the answer is no, is there a finite $n$ such that every simple graph admits an $n$-layer circuit board decomposition (the generalization to more than two layers should be clear)?

Answer 1

The answer to your first question is no. Take $K_{11}$, which has 55 edges. Then one of $E_1$ and $E_2$ has at least $28$ edges. Say $|E_1|\geq 28$. On the other hand, any planar graph satisfies $|E|\leq 3|V|-6$, and so if $(V,E_1)$ was planar, then $28\leq |E_1|\leq 33-6=27$, a contradiction.

Just to complete this answer (even though I like the Ramsey number idea better), for any potential $n$, choose $m$ such that $$\frac{m(m-1)}{6m-12}>n,$$ then run through the above argument using $K_m$.

Answer 2

Suppose there is a number n such that you can make an n-layered chip of any graph. Take a complete graph on $R(\underbrace{5,5\dots5,5}_n)$ vertices (R means ramsey's number). Then every n layering of the graph corresponds to a coloring with n colors of that graph. But by ramsey's theorem a complete graph of that size must contain a $K_5$ of only one color. Meaning the chip in the layer corresponding to that color is not planar.

---

I'm really just writing what Bof commented on casteel's answer.

Answer 3

I claimed in a comment that if you're allowed to subdivide an edge $u-v$ to $u-x_1-x_2-\cdots-v$ by introducing new vertices of degree 2, then any graph can be embedded on a circuit board.

The construction is simple. First embed the graph in a plane. Some of the edges may cross, and we can assume that the embedding is in so-called "general position" in which no crossing point is the intersection of more than two edges. (Multiple crossing points can be slightly perturbed to turn into groups of single crossing points.)

Now suppose that edge $a-b$ crosses $c-d$. We want to eliminate this crossing. Subdivide $c-d$ to $c-c'-d'-d$ so that $a-b$ crosses $c'-d'$, and $c'-d'$ is short enough that it doesn't intersect any other edge. This can be accomplished just by making $c'-d'$ sufficiently short. Then just move $c'-d'$ to the other side of the circuit board to eliminate the crossing.

Repeat this process for each of the other crossings.