Subdivisões de Orientações do Grafo Bipartido Completo K2,3 - Serra, Philipe M.; Maia, Ana Karolinna (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da Computação, 2025)
Neste trabalho, exploramos o problema de encontrar uma subdivisão em um digrafo F em um digrafo D, com o objetivo de identificar instâncias Polinomiais e NP-completas do mesmo. Mais especificamente, focamos nos casos em que F é uma orientação do K 2,3 , na tentativa de ter uma visão mais clara sobre uma conjectura à respeito do problema em grafos planares. Apresentamos todas as possíveis orientações do K 2,3 e os casos que o problema pode ser resolvidos de maneira polinomial, utilizando fluxos ou Teorema do Grid Direcionado. A complexidade de apenas um caso permanece em aberto.