ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
Characterising circular-arc contact B0–VPG graphs
Autor/es:
BONOMO-BRABERMAN, FLAVIA; GONZALEZ, CAROLINA LUC√ćA; GALBY, ESTHER
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2020 vol. 283 p. 435 - 443
ISSN:
0166-218X
Resumen:
A contact B0–VPG graph is a graph for which there exists a collection of nontrivial pairwise interiorly 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 touch. It was shown in Deniz et al. (2018) that RECOGNITION is NP-complete for contact B0–VPG graphs. In this paper we present a minimal forbidden induced subgraph characterisation of contact B0–VPG graphs within the class of circular-arc graphs and provide a polynomial-time algorithm for recognising these graphs.