K-SUN BELONGS TO HELLY B2-EPG
DOI:
https://doi.org/10.20873/uft.2447-4266.2023v9n1a25ptKeywords:
B2-EPG, Graph Theory, Intersection Graphs, Helly Property, k-sun GraphsAbstract
In this article we explore the -EPG class and the Helly property. We present generic results on EPG representations and define terms that support the other results, in addition, we finish the research with an unpublished algorithm that builds a Helly -EPG representation of any k-sun graph.
Downloads
References
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.
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Observatory Journal
This work is licensed under 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.
