Vi studerar terrängsiktsgrafer, en välkänd grafklass nära relaterad till polygonsiktsgrafer i beräkningsgeometri, för vilken en exakt grafteoretisk karakterisering fortfarande är okänd. Under det senaste årtiondet har terrängsiktsgrafer uppmärksammats i samband med tidsserieanalys med olika praktiska tillämpningar inom områden som fysik, geografi och medicinsk vetenskap. Vi gör framsteg i att förstå terrängsiktsgrafer genom att ge flera graf-teoretiska resultat. Vi visar till exempel att de inte kan innehålla antihål som är större än fem. Dessutom får vi två algoritmiska resultat. Vi utformar en snabb output-känslig kortaste vägen algoritm på godtyckliga inducerade subgrafer av terrängsikt grafer och en polynom-tid algoritm för Dominating Set på speciella terräng synbarhet grafer (kallas tratt synbarhet grafer).
Vissa graf-teoretiska resultat om (förbjudna) inducerade subgrafer av terrängsiktsgrafer och relation till andra grafklasser är kända REF.
Advancing Through Terrains
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}