8
$\begingroup$

Thor Johnson, et al, in their paper: Directed Tree Width, 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$).

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Hermann Gruber
    Oct 23, 2012 at 21:08

2 Answers 2

Reset to default
10
$\begingroup$

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. 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

Improve this answer
$\endgroup$
0
8
$\begingroup$

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, 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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Chandra Chekuri
    Jan 4, 2013 at 7:52
  • 1
    $\begingroup$ @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). $\endgroup$
    – Saeed
    Jan 4, 2013 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.