Vi undersöker klassen av vertex skärningsdiagram av sökvägar på ett rutnät, och särskilt överväga de underklasser som erhålls när varje sökväg i representationen har som mest k böjar (svängar). Vi kallar en sådan underklass B k-VPG grafer, k ≥ 0. Vid chiptillverkning modelleras kretslayout som banor (trådar) på ett rutnät, där det är naturligt att begränsa antalet kurvor per tråd av genomförbarhetsskäl och minska kostnaden för chipet. Om antalet k av kurvor inte är begränsat, då VPG grafer är likvärdiga med den välkända klassen av stränggrafer, nämligen skärningsdiagram över godtyckliga kurvor i planet. När det gäller B 0 -VPG grafer, observerar vi att horisontella och vertikala segment har stark Helly nummer 2, och därmed klique problemet har polynom-tid komplexitet, med tanke på vägen representation. Problemen med igenkänning och färgning för B 0 -VPG-grafer är dock NPfullständiga. Vi ger en 2- approximation algoritm för att färga B 0 -VPG grafer. Dessutom visar vi att triangelfria B 0 -VPG grafer är 4-färgade, och detta är bäst möjligt. Vi presenterar en hierarki av VPG diagram som relaterar dem till andra kända familjer av grafer. Rutnätet skärningsgrafer visas vara likvärdiga med bipartite B 0 -VPG grafer och cirkel grafer är strikt inneslutna i B 1 -VPG. Vi bevisar den strikta inneslutningen av B 0 -VPG i B 1 -VPG, och vi antar att denna strikt inneslutning i allmänhet fortsätter för alla värden av k. Vi presenterar en graf som inte är i B 1 -VPG. Planar grafer är kända för att vara i klassen av stränggrafer, och vi bevisar här att planar grafer är B 3 -VPG grafer, även om det inte är känt om detta är bäst möjligt.
Å andra sidan kan Max Clique problem för B 0 -VPG-grafer lösas i polynom tid, medan Vertex Colorability förblir NPfullständig men möjliggör en 2- approximation REF.
Vertex Intersection Graphs of Paths on a Grid
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}