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...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Articulo Preprint |
| Lenguaje: | Inglés |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/125545 |
| Aporte de: |
| Sumario: | 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. |
|---|