ON CONTACT B0–VPG GRAPHS WITH BOUNDED NUMBER OF HOLES

FLAVIA BONOMO; ESTHER GALBY; CAROLINA LUCÍA GONZALEZ; MARÍA PÍA MAZZOLENI

Encuentro Virtual

Congreso; VIII MACI 2021 - Congreso de Matemática Aplicada, Computacional e Industrial; 2021

A contact B0–VPG graph is a graph for which there exists a collection of nontrivial pairwiseinteriorly disjoint horizontal and vertical segments in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding segments share a grid-point that is an endpoint of at least one of the two segments. We present a polynomial-time algorithm that, for a constant c ∈ N, determines if a {C_i, with i≥c}–free graph with bounded number of holes (cycles of length at least four) is contact B0–VPG.