Representações de grafos Split e Ciclo EPG em grades minimais
Resumo
No presente artigo, abordamos a construção de representações minimais B1-EPG em grafos Split, em particular a subclasse Threshold, e grafos Ciclo.
Referências
Asinowski, A. and Ries, B. (2012). Some properties of edge intersection graphs of single-bend paths on a grid. Discrete Mathematics, 312(2):427–440.
Brady, M. L. and Sarrafzadeh, M. (1990). Stretching a knock-knee layout for multilayer wiring. IEEE Transactions on Computers, 39(1):148–151.
Cameron, K., Chaplick, S., and Hoàng, C. T. (2016). Edge intersection graphs of L-shaped paths in grids. Discrete Applied Mathematics, 210:185–194.
Chmeiss, A. and Jégou, P. (1997). A generalization of chordal graphs and the maximum clique problem. Information Processing Letters, 62(2):61–66.
da Fonseca Ramos, I. (2014). O POSTO DE UMA CONVEXIDADE DE GRAFOS. PhD thesis, Universidade Federal do Rio de Janeiro.
Deniz, Z., Nivelle, S., Ries, B., and Schindl, D. (2018). On split B1-EPG graphs. In Latin American Symposium on Theoretical Informatics, pages 361–375. Springer.
Deniz, Z., Nivelle, S., Ries, B., and Schindl, D. (2021). On some subclasses of split B1-EPG graphs. In Latin American Symposium on Theoretical Informatics, pages 625–636. Springer.
dos Santos Marinho, L. F., Silva, K. A., and dos Santos, T. D. (2023). B2-EPG split. Academic Journal on Computing, Engineering and Applied Mathematics, 4(1):1–7.
Golumbic, M. C., Lipshteyn, M., and Stern, M. (2009). Edge intersection graphs of single bend paths on a grid. Networks: An International Journal, 54(3):130–138.
Molitor, P. (1991). A survey on wiring. Elektronische Informationsverarbeitung und Kybernetik, 27(1):3–19.
Sinden, F. W. (1966). Topology of thin film RC circuits. Bell System Technical Journal, 45(9):1639–1662.
Brady, M. L. and Sarrafzadeh, M. (1990). Stretching a knock-knee layout for multilayer wiring. IEEE Transactions on Computers, 39(1):148–151.
Cameron, K., Chaplick, S., and Hoàng, C. T. (2016). Edge intersection graphs of L-shaped paths in grids. Discrete Applied Mathematics, 210:185–194.
Chmeiss, A. and Jégou, P. (1997). A generalization of chordal graphs and the maximum clique problem. Information Processing Letters, 62(2):61–66.
da Fonseca Ramos, I. (2014). O POSTO DE UMA CONVEXIDADE DE GRAFOS. PhD thesis, Universidade Federal do Rio de Janeiro.
Deniz, Z., Nivelle, S., Ries, B., and Schindl, D. (2018). On split B1-EPG graphs. In Latin American Symposium on Theoretical Informatics, pages 361–375. Springer.
Deniz, Z., Nivelle, S., Ries, B., and Schindl, D. (2021). On some subclasses of split B1-EPG graphs. In Latin American Symposium on Theoretical Informatics, pages 625–636. Springer.
dos Santos Marinho, L. F., Silva, K. A., and dos Santos, T. D. (2023). B2-EPG split. Academic Journal on Computing, Engineering and Applied Mathematics, 4(1):1–7.
Golumbic, M. C., Lipshteyn, M., and Stern, M. (2009). Edge intersection graphs of single bend paths on a grid. Networks: An International Journal, 54(3):130–138.
Molitor, P. (1991). A survey on wiring. Elektronische Informationsverarbeitung und Kybernetik, 27(1):3–19.
Sinden, F. W. (1966). Topology of thin film RC circuits. Bell System Technical Journal, 45(9):1639–1662.
Publicado
21/07/2024
Como Citar
DIAS, João Vitor Reis; SANTOS, Tanilson Dias dos.
Representações de grafos Split e Ciclo EPG em grades minimais. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 129-133.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.3099.
