Characterising circular-arc contact B0-VPG graphs

BONOMO, FLAVIA; GALBY, ESTHER; GONZALEZ, CAROLINA LUCÍA

Haifa

Workshop; 20th Haifa Workshop on Interdisciplinary Applications of Graphs, Combinatorics and Algorithms; 2020

Caesarea Rothschild Institute, University of Haifa, Israel

Let F be a nite 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 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 graph classes such as chordal, P5-free, P4-tidy, tree-cographs, 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.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.