On contact graphs of paths on a grid
| dc.contributor.author | Deniz, Zakir | |
| dc.contributor.author | Galby, Esther | |
| dc.contributor.author | Munaro, Andrea | |
| dc.contributor.author | Ries, Bernard | |
| dc.date.accessioned | 2020-04-30T13:32:55Z | |
| dc.date.available | 2020-04-30T13:32:55Z | |
| dc.date.issued | 2018 | |
| dc.department | DÜ, Fen-Edebiyat Fakültesi, Matematik Bölümü | en_US |
| dc.description | 26th International Symposium on Graph Drawing and Network Visualization, GD 2018 -- 26 September 2018 through 28 September 2018 -- 222189 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.identifier.doi | 10.1007/978-3-030-04414-5_22 | en_US |
| dc.identifier.endpage | 330 | en_US |
| dc.identifier.isbn | 9783030044138 | |
| dc.identifier.issn | 0302-9743 | |
| dc.identifier.scopusquality | Q3 | en_US |
| dc.identifier.startpage | 317 | en_US |
| dc.identifier.uri | https://dx.doi.org/10.1007/978-3-030-04414-5_22 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12684/485 | |
| dc.identifier.volume | 11282 LNCS | en_US |
| dc.indekslendigikaynak | Scopus | en_US |
| dc.language.iso | en | en_US |
| dc.publisher | Springer Verlag | en_US |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_US |
| dc.relation.publicationcategory | Konferans Öğesi - Uluslararası - Kurum Öğretim Elemanı | en_US |
| dc.rights | info:eu-repo/semantics/closedAccess | en_US |
| dc.title | On contact graphs of paths on a grid | en_US |
| dc.type | Conference Object | en_US |
Dosyalar
Orijinal paket
1 - 1 / 1
Küçük Resim Yok
- İsim:
- 0485.pdf
- Boyut:
- 448.57 KB
- Biçim:
- Adobe Portable Document Format
- Açıklama:
- Tam Metin / Full Text
