ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
Caracterización de los grafos B0-VPG de contacto dentro de la clase de los grafos arco-circulares
Autor/es:
GALBY, ESTHER; BONOMO-BRABERMAN, FLAVIA; CAROLINA LUCÍA GONZÁLEZ
Lugar:
Mendoza
Reunión:
Encuentro; LXVIII Reunión Anual de Comunicaciones Científicas; 2019
Institución organizadora:
Unión Matemática Argentina y Sociedad de Matemática de Chile
Resumen:
Dados un conjunto de elementos A y una familia F finita de subconjuntos de A, el grafo intersección de F es aquel cuyos vértices están en una correspondencia uno a uno con los elementos de F y además dos vértices son adyacentes si y solo si sus correspondientes elementos de F tienen intersección no vacía. Un grafo es arco-circular si es el grafo intersección de alguna familia finita de arcos de una misma circunferencia. Un grafo se dice B0-VPG de contacto si es el grafo de intersección de una familia de segmentos horizontales y verticales en una grilla, los cuales se pueden tocar pero no cruzar ni superponer. En [3] se muestra que el problema de reconocimiento de esta última clase de grafos es NP-completo, sin embargo existen algoritmos polinomiales de reconocimiento y caracterizaciones por subgrafos inducidos prohibidos minimales para algunas clases de grafos, como cordales, P4-tidy y bipartitos planares (ver [1,2,4]).En este trabajo presentamos una caracterización por subgrafos inducidos prohibidos minimales de los grafos B0-VPG de contacto dentro de la clase de los grafos arco-circulares y además proveemos un algoritmo de tiempo polinomial para reconocer dichos grafos.[1] F. Bonomo, M. P. Mazzoleni, M. L. Rean y B. Ries. On some special classes of contact B0-VPG graphs. arXiv:1807.07372. Manuscrito (2018).[2] F. Bonomo, M. P. Mazzoleni, M. L. Rean y B. Ries. Characterising Chordal Contact B0-VPG Graphs. Lecture Notes in Computer Science (ISCO 2018)[3] Z. Deniz, E. Galby, A. Munaro y B. Ries. On contact graphs of paths on a grid. Graph Drawing and Network Visualization, 317-330 (2018).[4] H. de Fraysseix, P. Ossona de Mendez y J. Pach. Representation of planar graphs by segments. Intuitive Geometry 63, 453-463 (1991).