K-SUN PERTENCE A B2-EPG-HELLY

Autores

DOI:

https://doi.org/10.20873/uft.2447-4266.2023v9n1a25pt

Palavras-chave:

B2-EPG, Graph Theory, Intersection Graphs, Helly Property, k-sun Graphs

Resumo

Neste artigo exploramos a classe de grafos -EPG e a propriedade Helly. Apresentamos resultados genéricos sobre representações EPG e definimos termos que suportam os demais resultados, além disso, apresentamos um algoritmo inédito que constrói uma representação -EPG-Helly de qualquer grafo k-sun.

Downloads

Não há dados estatísticos.

Biografia do Autor

Tanilson Dias dos Santos, Universidade Federal do Tocantins

Doutor em Engenharia de Sistemas e Computação - PESC/COPPE-UFRJ. Professor do Curso de Ciência da Computação - Universidade Federal do Tocantins. tanilson.dias@mail.uft.edu.br

Kedson Silva, Universidade Federal do Tocantins

Bacharel em Ciência da Computação – Universidade Federal do Tocantins. alves.kedson@mail.uft.edu.br

Luiz Fernando dos Santos Marinho, Universidade Estadual do Tocantins

Bacharel em Ciência da Computação – Universidade Federal do Tocantins. fernando.marinho@mail.uft.edu.br

Referências

ALCÓN, L., BONOMO, F., DURÁN, G., GUTIERREZ, M., MAZZOLENI, M. P., RIES, B., & VALENCIA-PABON, M. On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid. Discrete applied mathematics, 234, 12-21, 2018.

ALCÓN, L.; MAZZOLENI, M. P.; SANTOS, T. D. Relationship among B1-EPG, VPT and EPT graphs classes. Discussiones Mathematicae Graph Theory, 2021.

ASINOWSKI, A.; SUK, A. Edge intersection graphs of systems of paths on a grid with a bounded number of bends. Discrete Applied Mathematics, v. 157, n. 14, p. 3174-3180, 2009.

CAMERON, K.; CHAPLICK, S.; HOÀNG, C. T. Edge intersection graphs of L-shaped paths in grids. Discrete Applied Mathematics, v. 210, p. 185-194, 2016.

CELA, E.; GAAR, E. Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid. arXiv preprint arXiv:1908.01981, 2019.

FRANCIS, M. C.; LAHIRI, A. VPG and EPG bend-numbers of Halin graphs. Discrete Applied Mathematics, v. 215, p. 95-105, 2016.

GOLUMBIC, M. C.; LIPSHTEYN, M.; STERN, M. Edge intersection graphs of single bend paths on a grid. Networks: An International Journal, v. 54, n. 3, p.130-138, 2009.

GOLUMBIC, M. C.; LIPSHTEYN, M.; STERN, M. Single bend paths on a grid have strong helly number 4: errata atque emendationes ad “edge intersection graphs of single bend paths on a grid”. Networks, v. 62, n. 2, p. 161-163, 2013.

HELDT, D.; KNAUER, K.; UECKERDT, T. Edge-intersection graphs of grid paths: the bend number. Discrete Applied Mathematics, v. 167, p. 144-162, 2014.

HELDT, D.; KNAUER, K.; UECKERDT, T. On the bend-number of planar and outerplanar graphs. Discrete Applied Mathematics, v. 179, p. 109-119, 2014.

MARINHO, L. F. S.; SILVA, K. A.; SANTOS, T. D. B2-EPG Split. Academic Journal on Computing, Engineering and Applied Mathematics, v. 4, n. 1, p. 1-7, 2023.

PERGEL, M.; RZĄŻEWSKI, P. On edge intersection graphs of paths with 2 bends. Discrete Applied Mathematics, v. 226, p. 106-116, 2017.

STERN, M.; BIEDL, T. On edge-intersection graphs of k-bend paths in grids. Discrete Mathematics & Theoretical Computer Science, v. 12, 2010.

SZWARCFITER, J. L., SOUZA, U. S., SANTOS, T. D., GOLUMBIC, M. C., & BORNSTEIN, C. F. The Complexity of Helly-B_1-EPG Graph Recognition. Discrete Mathematics & Theoretical Computer Science, 22, 2020.

Downloads

Publicado

2023-12-31

Como Citar

DIAS DOS SANTOS, Tanilson; SILVA, Kedson; MARINHO, Luiz Fernando dos Santos. K-SUN PERTENCE A B2-EPG-HELLY. Revista Observatório , [S. l.], v. 9, n. 1, p. a25pt, 2023. DOI: 10.20873/uft.2447-4266.2023v9n1a25pt. Disponível em: https://sistemas.uft.edu.br/periodicos/index.php/observatorio/article/view/15720. Acesso em: 29 abr. 2024.

Edição

v. 9 n. 1 (2023): Teaching, Training and New Communication and Information Technologies / Ensino, Formação e Novas Tecnologias da Comunicação e da Informação

Seção

Ensino, Formação e Novas Tecnologias da Comunicação e da Informação

Licença

Copyright (c) 2023 Revista Observatório

Creative Commons License

Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.

[PT] Autores que publicam nesta revista concordam com os seguintes termos: 

1. Autores mantém os direitos autorais e concedem à revista, sem pagamento, o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License (CC BY-NC 4.0), permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista. 

Leia todos os termos dos direitos autorais aqui.