Subdivisions of Orientations of the Complete Bipartite Graph K2,3
Abstract
In this work, we explore the problem of finding a subdivision of a digraph F in a digraph D, with the goal of identifying polynomial-time and NP-complete instances of the problem. More specifically, we focus on the cases where F is an orientation of K2,3, in an attempt to gain a clearer understanding of a conjecture regarding the problem in planar graphs. We present all possible orientations of K2,3 and the cases where the problem can be solved in polynomial time, using flow techniques or the Directed Grid Theorem. The complexity of only one case remains open.
References
Bang-Jensen, J., Havet, F., and Maia, A. K. (2015). Finding a subdivision of a digraph. Theoretical Computer Science, 562:283 – 303.
Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The strong perfect graph theorem. Ann. of Math. (2), 164(1):51–229.
Chudnovsky, M. and Seymour, P. (2007). Excluding induced subgraphs. In Surveys in combinatorics 2007, volume 346 of London Math. Soc. Lecture Note Ser., pages 99–119. Cambridge Univ. Press, Cambridge.
Chudnovsky, M. and Seymour, P. (2010). The three-in-a-tree problem. Combinatorica, 30(4):387–417.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111 – 121.
Granot, D., Granot, F., and Zhu, W. R. (2000). Naturally submodular digraphs and forbidden digraph configurations. Discrete Appl. Math., 100(1-2):67–84.
Johnson, T., Robertson, N., Seymour, P. D., and Thomas, R. (2001). Directed tree-width. J. Combin. Theory Ser. B, 82(1):138–154.
Kawarabayashi, K.-i. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing.
Lévêque, B., Lin, D. Y., Maffray, F., and Trotignon, N. (2009). Detecting induced subgraphs. Discrete Appl. Math., 157(17):3540–3551.
Robertson, N. and Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65–110.
Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The strong perfect graph theorem. Ann. of Math. (2), 164(1):51–229.
Chudnovsky, M. and Seymour, P. (2007). Excluding induced subgraphs. In Surveys in combinatorics 2007, volume 346 of London Math. Soc. Lecture Note Ser., pages 99–119. Cambridge Univ. Press, Cambridge.
Chudnovsky, M. and Seymour, P. (2010). The three-in-a-tree problem. Combinatorica, 30(4):387–417.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111 – 121.
Granot, D., Granot, F., and Zhu, W. R. (2000). Naturally submodular digraphs and forbidden digraph configurations. Discrete Appl. Math., 100(1-2):67–84.
Johnson, T., Robertson, N., Seymour, P. D., and Thomas, R. (2001). Directed tree-width. J. Combin. Theory Ser. B, 82(1):138–154.
Kawarabayashi, K.-i. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing.
Lévêque, B., Lin, D. Y., Maffray, F., and Trotignon, N. (2009). Detecting induced subgraphs. Discrete Appl. Math., 157(17):3540–3551.
Robertson, N. and Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65–110.
Published
2025-07-20
How to Cite
SERRA, Philipe M.; MAIA, Ana Karolinna.
Subdivisions of Orientations of the Complete Bipartite Graph K2,3. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 138-142.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.9473.
