Journal article

Characterising Chordal Contact : Bo-VPG Graphs

Show more…
    2018
Published in:
  • Lecture Notes in Computer Science. - 2018, vol. 10856, p. 89-100
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
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/307913
Statistics

Document views: 20 File downloads:
  • isco2018_rero.pdf: 1