Geodesic
Planarity testing and constructing the topological drawing of a~plane graph (DFS)
Prikladnaâ diskretnaâ matematika, no. 2 (2016), pp. 100-114.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\mathrm O(m^2)$, where $m$ is the number of edges in the graph.
Keywords: graph, planarity, graph visualization, topological graph drawing, graph algorithms, isometric cycles.
Mots-clés : vertices rotation 
@article{PDM_2016_2_a6,
     author = {S. V. Kurapov and M. V. Davidovsky},
     title = {Planarity testing and constructing the topological drawing of a~plane graph {(DFS)}},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {100--114},
     publisher = {mathdoc},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_2_a6/}
}
TY  - JOUR
AU  - S. V. Kurapov
AU  - M. V. Davidovsky
TI  - Planarity testing and constructing the topological drawing of a~plane graph (DFS)
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 100
EP  - 114
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_2_a6/
LA  - ru
ID  - PDM_2016_2_a6
ER  - 
%0 Journal Article
%A S. V. Kurapov
%A M. V. Davidovsky
%T Planarity testing and constructing the topological drawing of a~plane graph (DFS)
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 100-114
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_2_a6/
%G ru
%F PDM_2016_2_a6
S. V. Kurapov; M. V. Davidovsky. Planarity testing and constructing the topological drawing of a~plane graph (DFS). Prikladnaâ diskretnaâ matematika, no. 2 (2016), pp. 100-114. http://geodesic.mathdoc.fr/item/PDM_2016_2_a6/

[1] Kurapov S. V., Davidovskiy M. V., “Two approaches to connections conducting in flat form factor”, Komponenty i Tekhnologii, 2015, no. 7, 142–147 (in Russian)

[2] Kurapov S. V., Davidovskiy M. V., “Topological approach to connections conducting in flat form factor”, Komponenty i Tekhnologii, 2015, no. 11, 127–130 (in Russian)

[3] Apanovich Z. V., From Graphs Drawing to Information Visualization, Preprint No 148, IIS RAS SB Publ., Novosibirsk, 2007, 16 pp. (in Russian)

[4] Di Battista G., Eades P., Tamassia R., Tollis I. G., “Algorithms for drawing graphs: an annotated bibliography”, Comp. Geom., 4:5 (1994), 235–282 | DOI | MR | Zbl

[5] Tamassia R., Handbook of Graph Drawing and Visualization, Chapman and Hall/CRC, Boca Raton, 2013, 844 pp. | MR

[6] Kurapov S. V., Tolok A. V., “The topological drawing of a graph: Construction methods”, Automation and Remote Control, 74:9 (2013), 1494–1509 | DOI | MR | Zbl

[7] Kavitha T., Liebchen C., Mehlhorn K., et al., “Cycle bases in graphs – characterization, algorithms, complexity, and applications”, Comput. Sci. Rev., 2009, 199–243 | Zbl

[8] Deza M., Grishukhin V. P., Shtogrin M. I., Isometric Polyhedral Subgraphs in Hypercubes and Cubic Lattices, MCCME Publ., Moscow, 2007, 192 pp. (in Russian)

[9] Ringel' G., Theorem of Maps Coloring, Mir Publ., Moscow, 1977, 126 pp. (in Russian) | MR

[10] Zykov A. A., Finite Graphs Theory, Nauka Publ., Novosibirsk, 1969, 554 pp. (in Russian)

[11] Swamy M. N. S., Thulasiraman K., Graphs, Networks and Algorithms, Wiley, 1980, 612 pp. | MR

[12] Harary F., Graph Theory, Addison Wesley, 1969 | MR | MR | Zbl

[13] Mak-Leyn S., “A combinatorial condition for planar graphs”, Kiberneticheskiy Sbornik. Novaya Seriya, 1970, no. 7, 68–77 (in Russian)

[14] Khopkroft Dzh. E., Tar'yan R. E., “The isomorphism of planar graphs”, Kiberneticheskiy Sbornik. Novaya seriya, 1975, no. 12, 39–61 (in Russian)

[15] Reingold E. M., Nievergelt J., Deo N., Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div., 1977 | MR | MR | Zbl

[16] Rappoport L. I., Morogovskiy B. N., Polivtsev S. A., “Vector algebra of intersections”, Mnogoprotsessornye vychislitel'nye struktury (Taganrog, TREI Publ.), 1980, no. 2(11), 53–56 (in Russian)