7
$\begingroup$

A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of a finite family of rays directed $\leftarrow$ or $\to$or $\uparrow$ in the plane. For example, $C_6$ is a 3DORG but not 2DORG. Can 3DORG be recognized efficiently?

Problem (Chaplick, Kindermann, Lipp, Wolff): Is the recognition of 3DORG in the class $\mathcal P$.

Here $\mathcal P$ is the class of problems of polynomial complexity.

(The problem was written 8.11.2015 by Alexander Wolff on page 19 of Volume 0 of the Lviv Scottish Book).

The prize for solution: Lunch in Würzburg.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ If somebody can edit to provide a more useful title (i.e., a title conveying some information to somebody who has no idea what a 3DORG is), it would be a useful contribution. As the description of the question is not clear enough for me to understand it, I'm unable to rewrite the title by myself. $\endgroup$
    – YCor
    Commented Oct 27, 2018 at 16:53
  • $\begingroup$ @YCor I have reformulated the title. Now is it more understandable? $\endgroup$
    – Lviv Scottish Book
    Commented Oct 27, 2018 at 18:28
  • $\begingroup$ The title is OK now (I edited to fix English). But my lack of understanding is unrelated to the title. I understand what is the intersection graph of a family of sets, and I don't see how to make things make sense (what exactly is a ray and how to define an intersection graph for these). $\endgroup$
    – YCor
    Commented Oct 27, 2018 at 18:32
  • 2
    $\begingroup$ a better reference is a paper page.math.tu-berlin.de/~felsner/Paper/gigdim.pdf $\endgroup$
    – Dima Pasechnik
    Commented Oct 27, 2018 at 19:27
  • 1
    $\begingroup$ On the question again, you use the words "effectively" and "efficiently". I'm not aware of a difference between these two words, and I'm not aware of a mathematical meaning for any of them. Also the title asks whether some problem has polynomial complexity, and the question does not refer to polynomial complexity. What is to be understood? For context, to start with, is there an algorithm at all? one can obviously enumerate all 3DORGS, and I can't say more. $\endgroup$
    – YCor
    Commented Oct 27, 2018 at 19:55

0

Reset to default

You must log in to answer this question.