Relationship among B₁-EPG, VPT and EPT graphs classes

This research contains as a main result the proof that every chordal B₁-EPG graph is simultaneously in the graph classes VPT and EPT. In addition, we describe structures that must be present in any B₁-EPG graph which does not admit a Helly-B1-EPG representation. In particular, this paper presents so...

Descripción completa

Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Mazzoleni, María Pía, Dias Dos Santos, Tanilson
Formato: Articulo
Lenguaje:Inglés
Publicado: 2023
Materias:
Ciencias Exactas
Matemática
edge-intersection of paths on a grid
edge-intersection graph of paths in a tree
Helly property
intersection graphs
single bend paths
vertex-intersection graph of paths in a tree
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/162664
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-162664
record_format dspace
spelling I19-R120-10915-1626642024-02-15T04:07:10Z http://sedici.unlp.edu.ar/handle/10915/162664 Relationship among B₁-EPG, VPT and EPT graphs classes Alcón, Liliana Graciela Mazzoleni, María Pía Dias Dos Santos, Tanilson 2023 2024-02-14T18:19:01Z en Ciencias Exactas Matemática edge-intersection of paths on a grid edge-intersection graph of paths in a tree Helly property intersection graphs single bend paths vertex-intersection graph of paths in a tree This research contains as a main result the proof that every chordal B₁-EPG graph is simultaneously in the graph classes VPT and EPT. In addition, we describe structures that must be present in any B₁-EPG graph which does not admit a Helly-B1-EPG representation. In particular, this paper presents some features of non-trivial families of graphs properly contained in Helly-B₁-EPG, namely bipartite, block, cactus and line graphs of bipartite graphs. Facultad de Ciencias Exactas Departamento de Matemática Articulo Articulo http://creativecommons.org/licenses/by-nc-nd/4.0/ Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) application/pdf 841-858
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Matemática
edge-intersection of paths on a grid
edge-intersection graph of paths in a tree
Helly property
intersection graphs
single bend paths
vertex-intersection graph of paths in a tree
spellingShingle Ciencias Exactas
Matemática
edge-intersection of paths on a grid
edge-intersection graph of paths in a tree
Helly property
intersection graphs
single bend paths
vertex-intersection graph of paths in a tree
Alcón, Liliana Graciela
Mazzoleni, María Pía
Dias Dos Santos, Tanilson
Relationship among B₁-EPG, VPT and EPT graphs classes
topic_facet Ciencias Exactas
Matemática
edge-intersection of paths on a grid
edge-intersection graph of paths in a tree
Helly property
intersection graphs
single bend paths
vertex-intersection graph of paths in a tree
description This research contains as a main result the proof that every chordal B₁-EPG graph is simultaneously in the graph classes VPT and EPT. In addition, we describe structures that must be present in any B₁-EPG graph which does not admit a Helly-B1-EPG representation. In particular, this paper presents some features of non-trivial families of graphs properly contained in Helly-B₁-EPG, namely bipartite, block, cactus and line graphs of bipartite graphs.
format Articulo
Articulo
author Alcón, Liliana Graciela
Mazzoleni, María Pía
Dias Dos Santos, Tanilson
author_facet Alcón, Liliana Graciela
Mazzoleni, María Pía
Dias Dos Santos, Tanilson
author_sort Alcón, Liliana Graciela
title Relationship among B₁-EPG, VPT and EPT graphs classes
title_short Relationship among B₁-EPG, VPT and EPT graphs classes
title_full Relationship among B₁-EPG, VPT and EPT graphs classes
title_fullStr Relationship among B₁-EPG, VPT and EPT graphs classes
title_full_unstemmed Relationship among B₁-EPG, VPT and EPT graphs classes
title_sort relationship among b₁-epg, vpt and ept graphs classes
publishDate 2023
url http://sedici.unlp.edu.ar/handle/10915/162664
work_keys_str_mv AT alconlilianagraciela relationshipamongb1epgvptandeptgraphsclasses
AT mazzolenimariapia relationshipamongb1epgvptandeptgraphsclasses
AT diasdossantostanilson relationshipamongb1epgvptandeptgraphsclasses
_version_ 1807222429351673856

Ejemplares similares