On the algorithm for constructing 2-connected minors of the Klein surface
Keywords:
граф-обструкція, поверхня Клейна, мінор, 2-зв’зністьAbstract
The paper considers the problem of constructing diagrams of 2-connected minors of the Klein surface, that is, the simple graphs of nonorientable genus 3 that are minimal with respect to the genus during compression or removal of an arbitrary edge of it. The main result is a linear algorithm. which correctly solves this problem.
References
Khomenko M.P. (1973). Topological aspects of graph theory. Kyiv: Preprint of the IM AHU. [in Ukrainian].
Khomenko M. P. (1970). -the transformation of graphs. Kyiv: Preprint of the IM AHU. [in Ukrainian].
Mohar B., Thomassen C. (2001). Graphs on Surfaces. Johns Hopkins University Press.
P. Skoda. (2012). Obstructions for embedding graphs into surfaces, Simon Frazer University, Ph.D. dissertation.
Petrenjuk V.I. (2021). On the structure of planar subgraphs of obstruction graphs of the nonorientable surface of a given genus. Physical-mathematical modeling and information technologies, 33, 105–109. Retrieved from: https://doi.org/10.15407/fmmit2021.33.105. [in Ukrainian].
Anna Flototto. (2010). Embeddability of graphs into the Klein surface. University Bielefeld. Ph.D. dissertation.
Hur Sur J. (2008). The Kuratowski covering conjecture for graphs of the order less than 10. Ohio State University, Ph.D. dissertation. Retrieved from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1209141894.
Petrenyuk V.I., Petrenyuk D.A., Orishaka O.V. (2022), The structure of projective planar subgraphs of graphs - obstructions of a given surface. Cybernetics and computer technologies, 2, 13-30. Retrieved from: http://cctech.org.ua/images/docs/Articles/2022/paper_22_2_2.pdf. [in Ukrainian].
