Polynomial-time recognition conjecture for APUD(1,1)

About 21 years old · traced to

Let GG be a graph, and let APUD(1,1)\mathrm{APUD}(1,1) denote the corresponding graph class of restricted disk intersection graphs.

APUD(1,1) recognition conjecture. Given a graph GG, it can be determined whether G∈APUD(1,1)G\in\mathrm{APUD}(1,1) in polynomial time.

The preceding characterization gives necessary structural conditions for connected graphs in APUD(1,1)\mathrm{APUD}(1,1), 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

Never refreshed

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.