On contact graphs of paths on a grid

Yükleniyor...
Küçük Resim

Tarih

2018

Dergi Başlığı

Dergi ISSN

Cilt Başlığı

Yayıncı

Springer Verlag

Erişim Hakkı

info:eu-repo/semantics/closedAccess

Özet

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. © Springer Nature Switzerland AG 2018.

Açıklama

26th International Symposium on Graph Drawing and Network Visualization, GD 2018 -- 26 September 2018 through 28 September 2018 -- 222189

Anahtar Kelimeler

Kaynak

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

WoS Q Değeri

Scopus Q Değeri

Q3

Cilt

11282 LNCS

Sayı

Künye