Rozpoznavani polygon-circle grafů a grafů intervalových filamentů je NP-úplné

Abstrakt

Dokazujeme, že problém rozpoznání dvou průnikových tříd je NP=úplný. A to konkrétně průnikových grafů konvexních polygonů vepsaných do kružnice (polygon-circle grafy) a průnikových grafů křivek nad intervaly na přímce (grafy intervalových filamentů).

Navíc ukážeme, že mezi těmito dvěma třídami se nevyskytuje žádná polynomiálně rozpoznatelná třída.

Klíčová slova

• Recognition
• Polygon-circle
• Graphs
• Graphs
• Interval
• Filaments
• NP-complete