Hinder av grafer har undersökts ganska intensivt under de senaste åren. Vi fokuserar på grafer som kan representeras av ett enda hinder. Med tanke på en (topologiskt öppen) polygon C och en ändlig uppsättning P punkter i allmän position i komplement till C, siktkurvan G C (P ) har en vertex för varje punkt i P och en kant pq för alla två punkter p och q i P som kan se varandra, det vill säga pq C = ∅. Vi ritar G C (P) rakt fram. Med tanke på en graf G, vill vi beräkna en hinder representation av G, det vill säga ett hinder C och en uppsättning punkter P sådan att G = G C (P ). Komplexiteten i detta problem är öppen, även för fallet att punkterna är exakt hörn av en enkel polygon och hindret är ett komplement till polygon-det enkla polygon synbarhet graf problem. Det finns två typer av hinder; ett inre hinder ligger i en begränsad del av komplementet till siktdragningen, medan ett yttre hinder ligger i den obundna komponenten. Vi visar att klassen grafer med en insida-obstacle representation är ojämförlig med den klass av grafer som har en yttre-obstacle representation. Vi visar vidare att varje graf med högst sju hörn eller omkrets högst 6 har en yttre-obstakel representation, som inte håller för en specifik graf med 8 hörn och omkrets 8. Slutligen, vi anser att den yttre obstacle graf sandwich problem: givna grafer G och H på samma vertex uppsättning, finns det en graf K sådan att G  på K och K har en utanför-obstacle representation? Vi visar att detta problem är NP-hård även för co-bipartite grafer. Med små ändringar, vårt bevis visar också att insidan-obstacle graf sandwich problem, den enda-obstacle graf sandwich problem, och den enkla-polygon synbarhet graf sandwich problem är alla NP-hård.
Den enda hårdhet resultat är NP-hårdhet av en "sandwich version" av igenkänningsproblem av polygon synbarhet grafer REF, d.v.s. besluta om för två indata grafer G  på H det finns en polygon synbarhet graf K med G  på K  på H är NP-hård.
Obstructing Visibilities with One Obstacle
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}