On Some Subclasses of Split B1 -EPG Graphs
No Thumbnail Available
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Science and Business Media Deutschland GmbH
Access Rights
info:eu-repo/semantics/closedAccess
Abstract
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.
Description
14th Latin American Symposium on Theoretical Informatics, LATIN 2020 -- 5 January 2021 through 8 January 2021 -- -- 252739
Keywords
Journal or Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
WoS Q Value
Scopus Q Value
Q3
Volume
12118 LNCS
