Sobre los grafos PVPG : una subclase de los grafos vértice intersección de caminos en una grilla.

LILIANA ALCÓN; FLAVIA BONOMO; MARÍA PÍA MAZZOLENI

Buenos Aires

Congreso; LXVI Reunión Anual de Comunicaciones Científicas. 2017; 2017

Los grafos vertice interseccion de caminos en una grilla (grafos VPG) son grafos cuyosvertices pueden ser representados como caminos en una grilla tal que dos vertices son adyacentes si y sólo si los caminos correspondientes comparten al menos un vertice de la grilla. Se sabe que reconocer a los grafos VPG es un problema NP-completo. En este trabajo, estudiamos la clase de los grafos PVPG, esta es una subclase de los grafos VPG tal que todos los caminos representantes estan entre dos rectas paralelas y tienen sus puntos nales sobre estas rectas. Probamos que PVPG = Co-comparabilidad. Mas aun, presentamos algunos subgrafos inducidos prohibidos minimales para la clase de los grafos B1-PVPG (esto es, grafos PVPG donde cada camino tiene a lo sumo un bend).