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

From papers

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

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.