Journal article

On contact graphs of paths on a grid

Show more…
    2018
Published in:
  • Lecture Notes in Computer Science. - 2018, vol. 11282, p. 317-330
English In this paper we consider Contact graphs of Paths on a Grid (CPG graphs), i.e. graphs for which there exists a family of interiorly disjoint paths on a grid in one-to-one correspondence with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. Our class generalizes the well studied class of VCPG graphs (see [1]). We examine CPG graphs from a structural point of view which leads to constant upper bounds on the clique number and the chromatic number. Moreover, we investigate the recognition and 3-colorability problems for B0- CPG, a subclass of CPG. We further show that CPG graphs are not necessarily planar and not all planar graphs are CPG.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Economics
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/307836
Statistics

Document views: 8 File downloads:
  • cpg-graphdrawing_rero.pdf: 8