Characterising Chordal Contact : Bo-VPG Graphs
- Bonomo, Flavia Universidad de Buenos Aires, Buenos Aires, Argentina
- Mazzoleni, Maria Pia Universidad Nacional de La Plata, La Plata, Argentina
- Rean, Mariano Leonardo Universidad de Buenos Aires, Buenos Aires, Argentina
- Ries, Bernard Université de Fribourg, Fribourg, Switzerland
-
2018
Published in:
- Lecture Notes in Computer Science. - 2018, vol. 10856, p. 89-100
Vertex intersection graphs
Contact Bo-VPG graph
Forbidden induced subgraphs
Chordal graphs
Polynomial-time algorithm
English
A graph G is a Bo- VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact Bo- VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph characterisation of contact Bo-VPG graphs within the class of chordal graphs and provide a polynomial-time algorithm for recognising these graphs.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
-
License undefined
- Identifiers
-
- RERO DOC 324624
- DOI 10.1007/978-3-319-96151-4_8
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307913
Export to…
Statistics
Document views: 215
File downloads:
- Document: 275