BECAS
GONZÁLEZ Carolina LucÍa
congresos y reuniones científicas
Título:
Characterising circular-arc contact B0-VPG graphs
Autor/es:
BONOMO-BRABERMAN, FLAVIA; GALBY, ESTHER; CAROLINA LUCÍA GONZÁLEZ
Lugar:
Haifa
Reunión:
Workshop; 20th Haifa Workshop on Interdisciplinary Applications of Graphs, Combinatorics and Algorithms; 2020
Institución organizadora:
Caesarea Rothschild Institute, University of Haifa
Resumen:
Let F be a finite family of non-empty sets. The intersection graph of F is a graph whose vertices are in a one-to-one correspondence with the sets in F such that two vertices are adjacent if and only if their corresponding sets in F have non-empty intersection.A graph is called contact B0-VPG if it is the intersection graph of a family of horizontal and vertical lines on a grid, which can touch each other at a grid-point but cannot cross nor share edges of the grid. It is shown in [4] that recognising the class of contact B0-VPG graphs is NP-complete, and the complete list of minimal forbidden induced subgraphs for the class is not known.Nevertheless, characterisations of contact B0-VPG graphs by minimal forbidden induced subgraphs are known restricted to some graphclasses such as chordal, P5-free, P4-tidy, tree-cographs [1,2], and most of them lead to polynomial time recognition algorithms within the class. Moreover, it is known that every bipartite planar graph is contact B0-VPG [3].In this work we present a minimal forbidden induced subgraph characterisation of contact B0-VPG graphs within the class of circular-arc graphs (i.e. intersection graphs of arcs on a circle) and provide a polynomial-time algorithm for recognising these graphs.[1] F. Bonomo, M.P. Mazzoleni, M.L. Rean, and B. Ries. Characterising Chordal Contact B0-VPG Graphs. In J. Lee, G. Rinaldi, and A. Ridha Mahjoub, editors, Proceedings of the International Symposium on Combinatorial Optimization 2018, volume 10856 of Lecture Notes in Computer Science, pages 89-100, 2018.[2] F. Bonomo-Braberman, M.P. Mazzoleni, M.L. Rean, and B. Ries. On some special classes of contact B0-VPG graphs. Discrete Applied Mathematics, in press, 2019, https://doi.org/10.1016/j.dam.2019.10.008.[3] H. de Fraysseix, P. Ossona de Mendez, and J. Pach. Representation of planar graphs by segments. Intuitive Geometry, 63:109-117, 1991.[4] Z. Deniz, E. Galby, A. Munaro, and B. Ries. On contact graphs of paths on a grid. In T. Biedl and A. Kerren, editors, Proceedings of the International Symposium on Graph Drawing and Network Visualization 2018, volume 11282 of Lecture Notes in Computer Science, pages 317-330, 2018.