On Some Subclasses of Split B1 -EPG Graphs

No Thumbnail Available

Date

2020

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

Issue

Citation