On some special classes of contact B<sub>0</sub>-VPG graphs

A graph G is a B<sub>0</sub>-VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B<sub>0</sub&g...

Descripción completa

Detalles Bibliográficos
Autores principales: Bonomo Braberman, Flavia, Mazzoleni, María Pía, Rean, Mariano Leonardo, Ries, Bernard
Formato: Articulo Preprint
Lenguaje:Inglés
Publicado: 2019
Materias:
Ciencias Exactas
Matemática
contact B 0-VPG graph
chordal graph
tree-cograph
P4-tidy graph
P5-free graph
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/125545
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-125545
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Matemática
contact B 0-VPG graph
chordal graph
tree-cograph
P4-tidy graph
P5-free graph
spellingShingle Ciencias Exactas
Matemática
contact B 0-VPG graph
chordal graph
tree-cograph
P4-tidy graph
P5-free graph
Bonomo Braberman, Flavia
Mazzoleni, María Pía
Rean, Mariano Leonardo
Ries, Bernard
On some special classes of contact B<sub>0</sub>-VPG graphs
topic_facet Ciencias Exactas
Matemática
contact B 0-VPG graph
chordal graph
tree-cograph
P4-tidy graph
P5-free graph
description A graph G is a B<sub>0</sub>-VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B<sub>0</sub>-VPG graph if it is a B<sub>0</sub>-VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B<sub>0</sub>-VPG graphs within four special graph classes: chordal graphs, tree-cographs, P<sub>4</sub>-tidy graphs and P5-free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B<sub>0</sub>-VPG graphs.
format Articulo
Preprint
author Bonomo Braberman, Flavia
Mazzoleni, María Pía
Rean, Mariano Leonardo
Ries, Bernard
author_facet Bonomo Braberman, Flavia
Mazzoleni, María Pía
Rean, Mariano Leonardo
Ries, Bernard
author_sort Bonomo Braberman, Flavia
title On some special classes of contact B<sub>0</sub>-VPG graphs
title_short On some special classes of contact B<sub>0</sub>-VPG graphs
title_full On some special classes of contact B<sub>0</sub>-VPG graphs
title_fullStr On some special classes of contact B<sub>0</sub>-VPG graphs
title_full_unstemmed On some special classes of contact B<sub>0</sub>-VPG graphs
title_sort on some special classes of contact b<sub>0</sub>-vpg graphs
publishDate 2019
url http://sedici.unlp.edu.ar/handle/10915/125545
work_keys_str_mv AT bonomobrabermanflavia onsomespecialclassesofcontactbsub0subvpggraphs
AT mazzolenimariapia onsomespecialclassesofcontactbsub0subvpggraphs
AT reanmarianoleonardo onsomespecialclassesofcontactbsub0subvpggraphs
AT riesbernard onsomespecialclassesofcontactbsub0subvpggraphs
bdutipo_str Repositorios
_version_ 1764820451838656514

Ejemplares similares