Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikl. Diskr. Mat., 2016, Number 2(32), Pages 100–114 (Mi pdm543)  

This article is cited in 3 scientific papers (total in 3 papers)

Applied Graph Theory

Planarity testing and constructing the topological drawing of a plane graph (DFS)

S. V. Kurapov, M. V. Davidovsky

Zaporizhzhya National University, Zaporizhzhya, Ukraine

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 $\mathrm O(m^2)$, where $m$ is the number of edges in the graph.

Keywords: graph, planarity, graph visualization, topological graph drawing, graph algorithms, vertices rotation, isometric cycles.

DOI: https://doi.org/10.17223/20710410/32/7

Full text: PDF file (1259 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.172

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

Citation in format AMSBIB
\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:
  • http://mi.mathnet.ru/eng/pdm543
  • http://mi.mathnet.ru/eng/pdm/y2016/i2/p100

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. 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  mathnet  crossref  isi  elib
    2. 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  mathnet  crossref
    3. 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  crossref  isi
  • Прикладная дискретная математика
    Number of views:
    This page:336
    Full text:244
    References:17

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021