On contact graphs of paths on a grid
- Deniz, Zakir Duzce University, Duzce, Turkey
- Galby, Esther Université de Fribourg, Fribourg, Switzerland
- Munaro, Andrea Université de Fribourg, Fribourg, Switzerland
- Ries, Bernard Université de Fribourg, Fribourg, Switzerland
-
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 et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Economics
- License
- License undefined
- Identifiers
-
- RERO DOC 324602
- DOI 10.1007/978-3-030-04414-5_22
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307836
Statistics
Document views: 26
File downloads:
- cpg-graphdrawing_rero.pdf: 66