On Some Subclasses of Split B1 -EPG Graphs
Küçük Resim Yok
Tarih
2020
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Springer Science and Business Media Deutschland GmbH
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
In this paper, we are interested in edge intersection graphs of paths in a grid, such that each path has at most one bend. These graphs were introduced in[14] and they are called B1-EPG graphs. We focus on split B1-EPG graphs, and study subclasses defined by restricting the paths to subsets of the four possible shapes (?, ?, ? and ? ). We first state that the set of minimal forbidden induced subgraphs for the class of split ? -path graphs is infinite. Then, we further focus on two subclasses, and provide finite forbidden induced subgraphs characterizations for all possible subclasses defined by restricting to any subset of shapes. © 2020, Springer Nature Switzerland AG.
Açıklama
14th Latin American Symposium on Theoretical Informatics, LATIN 2020 -- 5 January 2021 through 8 January 2021 -- -- 252739
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
12118 LNCS
