<p>Johnson et al shown that the planar digraphs are excluding $J_K$ as minor, but they never published this paper, because they were looking to generalize this result. But recently Ken-Ichi Kawarabayashi and Stephan Kreutzer proved "An Excluded Grid Theorem for Digraphs with Forbidden Minors" <a href="http://www.siam.org/meetings/da14/da14_accepted.pdf" rel="nofollow">SODA2014</a>, which generalizes grid theorem on planar directed graphs by Johnson et al. to digraphs with fix undirected minor excluded.</p>

<p><strong>EDIT:</strong> The aforementioned paper is now publicly available:</p>

<p><a href="http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.6" rel="nofollow">http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.6</a></p>

<p>Johnson et al. 2001 paper, now is publicly available:</p>

<p><a href="http://arxiv.org/abs/1510.00473" rel="nofollow">Excluding A Grid Minor In Planar Digraphs</a></p>

CC BY-SA 3.0
2013-01-04T07:52:43.537Z
I am interested in hearing about these results. I would appreciate you providing the recent references. Did you get the draft paper from Seymour etal?
Chandra Chekuri
CC BY-SA 3.0
2013-01-04T09:09:33.323Z
@ChandraChekuri, Actually someone else got draft paper (many years ago), and some days ago I just take a look at paper for few hours. on the first page, one of a main authors wrote "Do not distribute". so we cannot expect to have it, but new result is going to publish in SODA2013, and I can refer to this new result (when published).
Saeed
CC BY-SA 3.0
2013-01-03T13:12:21.953Z
2015-11-16T13:03:32.073Z
2015-11-16T13:03:32.073Z
Saeed
<p>There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs.</p>

<p>Stephan Kreutzer and Ken-ichi Kawarabayashi: <a href="http://arxiv.org/pdf/1411.5681v1.pdf" rel="nofollow">The directed grid theorem</a>.    arXiv:1411.5681 [cs.DM]  </p>

<p><strong>EDIT (June 16, 2015):</strong></p>

<p>A short version of their paper appears here:</p>

<p>Ken-ichi Kawarabayashi, Stephan Kreutzer. The Directed Grid Theorem. In: Rocco A. Servedio, Ronitt Rubinfeld (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing 2015. pp. 655-664</p>

CC BY-SA 3.0
2014-11-28T20:01:14.557Z
2015-06-16T20:08:44.473Z
2015-06-16T20:08:44.473Z
Hermann Gruber
<p>Thor Johnson, et al, in their paper: <a href="http://people.math.gatech.edu/~thomas/PAP/dirtree.pdf">Directed Tree Width</a>, introduced a definition for directed grid $J_k$, and they conjectured:</p>

<blockquote>
  <p>$(5.1)$ For every integer $k$ there exists an integer $N$ such that every
  digraph with tree-width $N$ or more has a minor isomorphic to $J_k$.</p>
</blockquote>

<p>And they continued by saying:</p>

<blockquote>
  <p>We have convinced ourselves that $(5.1)$ holds for planar digraphs,
  but the general case is open.</p>
</blockquote>

<p>And I'm looking for this unpublished paper (how they proved the conjecture for di-planar graphs), or related stuff in this case, actually how to use such a grid (I mean $J_k$).</p>

CC BY-SA 3.0
2012-10-23T21:08:33.463Z
Did you already contact the authors about that? I'd be curious about that, too. To me, the statement "We have convinced ourselves" does not necessarily imply that they had a fully worked out version of their argument.
Hermann Gruber
<reference-request><graph-theory><co.combinatorics><graph-minor>
Grid minor in digraphs
Saeed
# Grid minor in digraphs

(Asked by: username_0 on 2012-10-23)

Thor Johnson, et al, in their paper: [Directed Tree Width](http://people.math.gatech.edu/~thomas/PAP/dirtree.pdf), introduced a definition for directed grid $J\_k$, and they conjectured:

> $(5.1)$ For every integer $k$ there exists an integer $N$ such that every
> digraph with tree-width $N$ or more has a minor isomorphic to $J\_k$.

And they continued by saying:

> We have convinced ourselves that $(5.1)$ holds for planar digraphs,
> but the general case is open.

And I'm looking for this unpublished paper (how they proved the conjecture for di-planar graphs), or related stuff in this case, actually how to use such a grid (I mean $J\_k$).

**Tags:** reference-request, graph-theory, co.combinatorics, graph-minor
> **Comments:**
> **username_1**: Did you already contact the authors about that? I'd be curious about that, too. To me, the statement "We have convinced ourselves" does not necessarily imply that they had a fully worked out version of their argument.  

---

## 2 answers

### Answer by username_1 on 2014-11-28. Score: 10 | Accepted answer

There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs.

Stephan Kreutzer and Ken-ichi Kawarabayashi: [The directed grid theorem](http://arxiv.org/pdf/1411.5681v1.pdf). arXiv:1411.5681 [cs.DM]

**EDIT (June 16, 2015):**

A short version of their paper appears here:

Ken-ichi Kawarabayashi, Stephan Kreutzer. The Directed Grid Theorem. In: Rocco A. Servedio, Ronitt Rubinfeld (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing 2015. pp. 655-664


---

### Answer by username_0 on 2013-01-03. Score: 8

Johnson et al shown that the planar digraphs are excluding $J\_K$ as minor, but they never published this paper, because they were looking to generalize this result. But recently Ken-Ichi Kawarabayashi and Stephan Kreutzer proved "An Excluded Grid Theorem for Digraphs with Forbidden Minors" [SODA2014](http://www.siam.org/meetings/da14/da14_accepted.pdf), which generalizes grid theorem on planar directed graphs by Johnson et al. to digraphs with fix undirected minor excluded.

**EDIT:** The aforementioned paper is now publicly available:

<http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.6>

Johnson et al. 2001 paper, now is publicly available:

[Excluding A Grid Minor In Planar Digraphs](http://arxiv.org/abs/1510.00473)

> **Comments:**
> **username_2**: I am interested in hearing about these results. I would appreciate you providing the recent references. Did you get the draft paper from Seymour etal?  
> **username_0**: @ChandraChekuri, Actually someone else got draft paper (many years ago), and some days ago I just take a look at paper for few hours. on the first page, one of a main authors wrote "Do not distribute". so we cannot expect to have it, but new result is going to publish in SODA2013, and I can refer to this new result (when published).  

---

