Enhet disk grafer är skärningsdiagram över enhet diameter stängda diskar i planet. Detta papper minskar SATIFIability till problemet med att känna igen enhet disk grafer. Likvärdigt visar det att bestämma om en graf har sfäricitet 2 eller mindre, även om grafen är plan eller är känd för att ha sfäricitet högst 3, är NP-hård. Vi visar hur denna minskning kan utvidgas till 3 dimensioner, vilket visar att enhet sfär graf igenkänning, eller avgöra om en graf har sfäricitet 3 eller mindre, är också NP-hård. Vi antar att K-sfären är NP-hård för alla xed K större än 1.
I REF visade Breu och Kirkpatrick att problemet med igenkänning av enhetsskivan är NP-hård.
Unit Disk Graph Recognition is NP-Hard
{'venue': 'Computational Geometry. Theory and Applications', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}