<p>I.1 Suppose we have two planar graphs <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with spanning tree count <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span> respectively then is there a graph construction in Logspace to get a planar graph from <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with spanning tree count <span class="math-container">$C_1C_2$</span> without knowing <span class="math-container">$C_1$</span> or <span class="math-container">$C_2$</span>?</p>
<p>I.2 How about if we are allowed to know <span class="math-container">$C_2$</span> alone?</p>
<p>II.1 Suppose we have two planar graphs <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with spanning tree count <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span> respectively then is there a graph construction in Logspace to get a planar graph from <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with spanning tree count <span class="math-container">$C_1+C_2$</span> without knowing <span class="math-container">$C_1$</span> or <span class="math-container">$C_2$</span>?</p>
<p>II.2 How about if we are allowed to know <span class="math-container">$C_2$</span> alone?</p>
<p>For properness assume the number of spanning tress is at least <span class="math-container">$3$</span> in <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span>.</p>

CC BY-SA 4.0
2023-08-31T05:44:59.930Z
I gather you assume the graphs to be connected.
Emil Jeřábek
CC BY-SA 4.0
2023-08-31T05:46:54.707Z
$C_1C_2$ is obvious: just take the disjoint union of the two graphs, and connect them by one edge (no matter which one).
Emil Jeřábek
CC BY-SA 4.0
2023-09-01T10:40:46.640Z
Do you know of any procedure which accomplishes II.1? For starters, does a planar graph with spanning tree count $C$ exist for every $C$, having size polynomial in $\log C$?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2023-09-01T17:29:37.710Z
@LieuweVinkhuijzen I do not know.
Turbo
<cc.complexity-theory><planar-graphs><logspace><determinant><spanning-tree>
Is there a construction which multiplies and adds spanning trees in Logspace?
Turbo
# Is there a construction which multiplies and adds spanning trees in Logspace?

(Asked by: username_0 on 2023-08-31)

I.1 Suppose we have two planar graphs $G\_1$ and $G\_2$ with spanning tree count $C\_1$ and $C\_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G\_1$ and $G\_2$ with spanning tree count $C\_1C\_2$ without knowing $C\_1$ or $C\_2$?

I.2 How about if we are allowed to know $C\_2$ alone?

II.1 Suppose we have two planar graphs $G\_1$ and $G\_2$ with spanning tree count $C\_1$ and $C\_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G\_1$ and $G\_2$ with spanning tree count $C\_1+C\_2$ without knowing $C\_1$ or $C\_2$?

II.2 How about if we are allowed to know $C\_2$ alone?

For properness assume the number of spanning tress is at least $3$ in $G\_1$ and $G\_2$.

**Tags:** cc.complexity-theory, planar-graphs, logspace, determinant, spanning-tree
> **Comments:**
> **username_1**: I gather you assume the graphs to be connected.  
> **username_1**: $C_1C_2$ is obvious: just take the disjoint union of the two graphs, and connect them by one edge (no matter which one).  
> **username_2**: Do you know of any procedure which accomplishes II.1? For starters, does a planar graph with spanning tree count $C$ exist for every $C$, having size polynomial in $\log C$?  
> **username_0**: @LieuweVinkhuijzen I do not know.  

---

## 0 answers

