Risultato della ricerca

Proper circular arc graphs as intersection graphs of pathson a grid

Galby, Esther ; Mazzoleni, María Pía ; Ries, Bernard

In: Discrete Applied Mathematics, 2019, vol. 262, p. 195-202

In this paper we present a characterization, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a grid, where each path has at most one bend (turn).

OPEN IN
SONAR

On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid

Alcón, Liliana ; Bonomo, Flavia ; Durán, Guillermo ; Gutierrez, Marisa ; Mazzoleni, María Pía ; Ries, Bernard ; Valencia-Pabon, Mario

In: Discrete applied mathematics, 2018, vol. 234, p. 12-21

Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex of the graph a nontrivial path on a rectangular grid such that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid. For a nonnegative integer k, Bk-EPG graphs are...

Perfeziona i miei risultati

Document type

Institution

Collection spécifique

Lingua

Autore