K-SUN APPARTIENT À B2-EPG-HELLY
DOI :
https://doi.org/10.20873/uft.2447-4266.2023v9n1a25ptMots-clés :
B2-EPG, Graph Theory, Intersection Graphs, Helly Property, k-sun GraphsRésumé
Dans cet article, nous explorons la classe de graphes B_2-EPG et la propriété Helly. Nous présentons des résultats génériques sur les représentations EPG et définissons les termes qui supportent les autres résultats, en plus, nous présentons un algorithme sans précédent qui construit une représentation B_2-EPG-Helly de tout graphe k-sun.
Téléchargements
Références
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.
Téléchargements
Publié-e
Comment citer
Numéro
Rubrique
Licence
(c) Tous droits réservés Observatoire Journal 2023
Cette œuvre est sous licence Creative Commons Attribution - Pas d'Utilisation Commerciale 4.0 International.
[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.
