Polynomial-time recognition conjecture for APUD(1,1)
Let be a graph, and let denote the corresponding graph class of restricted disk intersection graphs.
APUD(1,1) recognition conjecture. Given a graph , it can be determined whether in polynomial time.
The preceding characterization gives necessary structural conditions for connected graphs in , but the source does not establish that they are sufficient. Polynomial-time recognition therefore remains an open problem.
References
Primary source
Onur Çağırıcı, “Computational Aspects of Problems on Visibility and Disk Graph Representations”, arXiv:2111.00609 (2021).
Additional references
8 papers in this index state this conjecture (2005–2021). The statement above is taken from the most recent of them; the others are arXiv:1710.07748, arXiv:1512.03005, arXiv:1508.02940, arXiv:1411.7879, arXiv:0905.3252, arXiv:0902.0198, arXiv:cs/0501076.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.