<p>Just to complete my comment:</p>

<p>GG remains PSPACE-complete on planar bipartite directed graphs with maximum degree 3 (see<br>
<a href="http://doi.acm.org/10.1145/322186.322201" rel="nofollow noreferrer">D. Lichtenstein, M. Sipser: GO Is Polynomial-Space Hard. J. ACM 27(2): 393-401 (1980)</a> )</p>

<p>But (vertex) GG on undirected graphs is in P (see <a href="https://cstheory.stackexchange.com/q/25897/3247">this Q&amp;A</a> and <a href="http://www.sciencedirect.com/science/article/pii/030439759390026P" rel="nofollow noreferrer">this paper</a>) so it is in P also for grid graphs.</p>

<p>For directed solid grid graphs I didn't find any reference, however, I think there is an easy way to simulate a planar bipartite directed graph; the following idea should work:</p>

<p><img src="https://i.sstatic.net/GDgob.png" alt="enter image description here"><br>
Both the "diamond" structure (A) and the crossover gadget (C), can be converted into an equivalent (directed) solid grid graph gadget (B) and (D).</p>

CC BY-SA 3.0
2015-03-02T23:34:44.550Z
Ah cool. The reduction looks good to me. Nice use of the edges of the grey vertices to prevent a yellow vertex from ever being able to use them.
Quanquan Liu
CC BY-SA 3.0
2015-03-02T23:40:09.263Z
One thing to be careful about is the parity of the grid graph edges. If you're using more than one grid graph edge for each planar graph edge (the number of grid graph edges used to represent a single planar graph edge should be odd).
Quanquan Liu
CC BY-SA 3.0
2015-03-03T09:51:46.360Z
@q2liu: yes. The source graph is bipartite, so parity should not be an issue. In the graph (B) I "compacted" the diamonds: 1 blue edge -> 3 edges, 1 red edge -> 1 red edge; graph (D) is also "compacted".
Marzio De Biasi
CC BY-SA 3.0
2015-03-02T22:52:21.663Z
2015-03-02T22:58:02.497Z
2017-04-13T12:32:28.077Z
Marzio De Biasi
<p>A post here <a href="https://cstheory.stackexchange.com/questions/22445/for-which-families-of-graphs-is-generalized-geography-in-p">For which families of graphs is Generalized Geography in $P$?</a> mentioned that generalized geography on solid grid graphs is open. Is the question still open? A quick search on Google shows no results, but I wanted to see if anyone with more familiarity with the area can confirm.</p>

<p>Related to this question, I also wonder if Generalized Geography on grid graphs with holes or thin graphs are also open? What about on bipartite graphs, expander graphs...etc? </p>

CC BY-SA 3.0
2015-03-02T08:16:17.003Z
Up to my knowkledge: (vertex) GG on undirected graphs is in P (see [this Q&A](http://cstheory.stackexchange.com/q/25897/3247) and [this paper](http://www.sciencedirect.com/science/article/pii/030439759390026P)) so it is in P also for grid graphs. For directed bipartite graphs it remains PSPACE-complete. For directed solid grid graphs, I think there is an easy way to simulate a planar directed graph, and prove that it is PSPACE-complete (but I didn't find it in any paper).
Marzio De Biasi
CC BY-SA 3.0
2015-03-02T22:45:24.793Z
Is there a reference for directed bipartite graphs?
Quanquan Liu
<ds.algorithms><graph-theory><graph-algorithms><np-hardness>
Generalized geography on solid grid graphs
Quanquan Liu
# Generalized geography on solid grid graphs

(Asked by: username_0 on 2015-03-02)

A post here [For which families of graphs is Generalized Geography in $P$?](https://cstheory.stackexchange.com/questions/22445/for-which-families-of-graphs-is-generalized-geography-in-p) mentioned that generalized geography on solid grid graphs is open. Is the question still open? A quick search on Google shows no results, but I wanted to see if anyone with more familiarity with the area can confirm.

Related to this question, I also wonder if Generalized Geography on grid graphs with holes or thin graphs are also open? What about on bipartite graphs, expander graphs...etc?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, np-hardness
> **Comments:**
> **username_1**: Up to my knowkledge: (vertex) GG on undirected graphs is in P (see [this Q&A](http://cstheory.stackexchange.com/q/25897/3247) and [this paper](http://www.sciencedirect.com/science/article/pii/030439759390026P)) so it is in P also for grid graphs. For directed bipartite graphs it remains PSPACE-complete. For directed solid grid graphs, I think there is an easy way to simulate a planar directed graph, and prove that it is PSPACE-complete (but I didn't find it in any paper).  
> **username_0**: Is there a reference for directed bipartite graphs?  

---

## 1 answers

### Answer by username_1 on 2015-03-02. Score: 1 | Accepted answer

Just to complete my comment:

GG remains PSPACE-complete on planar bipartite directed graphs with maximum degree 3 (see  
[D. Lichtenstein, M. Sipser: GO Is Polynomial-Space Hard. J. ACM 27(2): 393-401 (1980)](http://doi.acm.org/10.1145/322186.322201) )

But (vertex) GG on undirected graphs is in P (see [this Q&A](https://cstheory.stackexchange.com/q/25897/3247) and [this paper](http://www.sciencedirect.com/science/article/pii/030439759390026P)) so it is in P also for grid graphs.

For directed solid grid graphs I didn't find any reference, however, I think there is an easy way to simulate a planar bipartite directed graph; the following idea should work:

![enter image description here](https://i.sstatic.net/GDgob.png)  
Both the "diamond" structure (A) and the crossover gadget (C), can be converted into an equivalent (directed) solid grid graph gadget (B) and (D).

> **Comments:**
> **username_0**: Ah cool. The reduction looks good to me. Nice use of the edges of the grey vertices to prevent a yellow vertex from ever being able to use them.  
> **username_0**: One thing to be careful about is the parity of the grid graph edges. If you're using more than one grid graph edge for each planar graph edge (the number of grid graph edges used to represent a single planar graph edge should be odd).  
> **username_1**: @q2liu: yes. The source graph is bipartite, so parity should not be an issue. In the graph (B) I "compacted" the diamonds: 1 blue edge -> 3 edges, 1 red edge -> 1 red edge; graph (D) is also "compacted".  

---

