Abstract:
In this article we present a new graph planarity testing algorithm along with the construction of mathematical framework used for representing topological drawings of plane graphs. This mathematical framework is based on the notions of graph isometric cycles and rotation of graph vertices. It is shown that the system of isometric cycles of a graph induces the rotation of its vertices for representing topological drawing of the plane graph. In contrast to the classical planarity testing algorithms, e.g. the Hopcroft–Tarjan algorithm, the topological drawing obtained as a result of the proposed algorithm execution is used subsequently for the visualization of the planar graph. Computational complexity of the proposed algorithm is estimated by O(m2), where m is the number of edges in the graph.
Citation:
S. V. Kurapov, M. V. Davidovsky, “Planarity testing and constructing the topological drawing of a plane graph (DFS)”, Prikl. Diskr. Mat., 2016, no. 2(32), 100–114
\Bibitem{KurDav16}
\by S.~V.~Kurapov, M.~V.~Davidovsky
\paper Planarity testing and constructing the topological drawing of a~plane graph (DFS)
\jour Prikl. Diskr. Mat.
\yr 2016
\issue 2(32)
\pages 100--114
\mathnet{http://mi.mathnet.ru/pdm543}
\crossref{https://doi.org/10.17223/20710410/32/7}
Linking options:
https://www.mathnet.ru/eng/pdm543
https://www.mathnet.ru/eng/pdm/y2016/i2/p100
This publication is cited in the following 4 articles:
A. G. Karpov, N. V. Egorov, “Algoritmy sostavleniya matematicheskoi modeli fizicheskikh sistem s pomoschyu grafov”, Vestn. S.-Peterburg. un-ta. Ser. 10. Prikl. matem. Inform. Prots. upr., 20:1 (2024), 10–19
A. G. Karpov, V. A. Klemeshev, D. Yu. Kuranov, “Opredelenie rabotosposobnosti sistemy, struktura kotoroi zadana grafom”, Vestn. S.-Peterburg. un-ta. Ser. 10. Prikl. matem. Inform. Prots. upr., 16:1 (2020), 41–49
A. G. Karpov, V. A. Klemeshev, D. Yu. Kuranov, “Determining the ability to work of the system, the structure of which is given using graph”, Vestn. St.-Peterbg. Univ. Ser. 10 Prikl. Mat. Inform. Protsessy, 16:1 (2020), 41–49
S. V. Kurapov, A. V. Tolok, “Construction of a topological drawing of the most planar subgraph of the non-planar graph”, Autom. Remote Control, 79:5 (2018), 793–810