On some special classes of contact B0-VPG graphs
BP2-STS
- Bonomo-Braberman, Flavia University of Buenos Aires, Argentina
- Mazzoleni, Maria Pia Universidad Nacional de la Plata, Argentina
- Rean, Leonardo University of Buenos Aires, Argentina
- Ries, Bernard ORCID Université de Fribourg, Switzerland
- 2019
Published in:
- Discrete Applied Mathematics. - Elsevier BV. - 2019, vol. 308, p. 111-129
English
A graph G is a B0-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 B0-VPG graph if it is a B0-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 B0-VPG graphs within four special graph classes: chordal graphs, tree-cographs, P4-tidy graphs and P5-free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B0-VPG graphs.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- Rights reserved
- Open access status
- green
- Identifiers
-
- DOI 10.1016/j.dam.2019.10.008
- ISSN 0166-218X
- Persistent URL
- https://folia.unifr.ch/unifr/documents/322640
Statistics
Document views: 14
File downloads:
- b0epgcopy.pdf: 51