Grafos arco-circulares como grafos de intersección por aristas de caminos en una grilla.

LILIANA ALCÓN; FLAVIA BONOMO; GUILLERMO DURÁN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI; BERNARD RIES; MARIO VALENCIA-PABON

Simposio; SIO 2016 - 14º Simposio Argentino de Investigación Operativa.; 2016

Golumbic, Lipshteyn y Stern probaron que todo grafo puede ser representado como el grafo arista intersección de caminos en una grilla, esto es, se puede asociar a cada vértice del grafo un camino no trivial en la grilla tal que dos vértices son adyacentes si y sólo si los correspondientes caminos comparten al menos una arista de la grilla. Para cualquier entero no negativo k, los grafos Bk-EPG son grafos que admiten un modelo en el cual cada camino tiene a lo sumo k bends. Los grafos arco-circulares son los grafos intersección de arcos abiertos en un círculo. Es fácil ver que todo grafo arco-circular es B4-EPG, embebiendo,  el círculo en un rectángulo de la grilla. En este trabajo probamos que todo grafo arco-circular es B3-EPG, pero si nos restringimos a representaciones rectangulares existen grafos que requieren caminos con cuatro bends. Además, mostramos que los grafos arco-criculares normales admiten representaciones rectangulares con a lo sumo dos bends por camino. Caracterizamos a los grafos que admiten representaciones rectangulares con a lo sumo un bend por camino por subgrafos inducidos prohibidos, y mostramos que ellos son una subclase de los grafos arco-circulares normal Helly.