تشخيص وترافزايشي بودن براي چند كلاس از گراف هاي هندسي

يك گراف هندسي را وترافزايشي گويند هرگاه بين هر دو رأس از گراف، مسيري وجود داشته باشد به طوري كهبراي هر چهار نقطهc ،b ،a وd كه به ترتيب روي مسير قرار گرفته اند، فاصله a و d از فاصله b و c كمتر نباشد. دراين مقاله نشان مي دهيم براي دورها و θ -گراف هاي هندسي با n رأس، در زمان $(O^2(n $ مي توان وترافزايشي بودن راتشخيص داد. براي گراف هايي كه هر يال آنها روي حداكثر يك دور قرار دارد و هر دور دقيقا يك رأس برشي دارد،مي توان در زمان $O( n^2+K^2n)$ كه k مجموع تعداد دورها و رئوس درجه يك گراف و n تعداد رئوس گراف است، وترافزايشي بودن را تشخيص داد. همچنين نشان مي دهيم تشخيص وترافزايشي بودن گراف هاي هندسي متعامد باn رأس وm يال در زمان (O(nm ممكن است.