Maximal Planarization of Non - Planar Graphs
Abstract This paper presents a MAXIMAL - PLANARIZE algorithm using EQUIVELANT - GRAPH procedure . The algorithm proceeds by embedding one or few edges at each stage , without creating nonplanarity of the resultant graph , and to construct a maximal planar subgraph G , of G directly . The present imp...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Unviversity of Technology- Iraq
2005-06-01
|
| Series: | Engineering and Technology Journal |
| Subjects: | |
| Online Access: | https://etj.uotechnology.edu.iq/article_182141_b3338db9e790682d3a8f812082b5bcd6.pdf |
| _version_ | 1797325095436288000 |
|---|---|
| author | Suzan Yacob |
| author_facet | Suzan Yacob |
| author_sort | Suzan Yacob |
| collection | DOAJ |
| description | Abstract This paper presents a MAXIMAL - PLANARIZE algorithm using EQUIVELANT - GRAPH procedure . The algorithm proceeds by embedding one or few edges at each stage , without creating nonplanarity of the resultant graph , and to construct a maximal planar subgraph G , of G directly . The present implementation shows that using two planarization algorithms is unnecessary because of their complexities . It runs in linear time to give a maximal planar subgraph and adds the maximum number of edges possible without creating nonplanarity , using only one simple and efficient algorithm . |
| first_indexed | 2024-03-08T06:06:11Z |
| format | Article |
| id | doaj.art-f9c8b15d41d645f780d435531f6dd05d |
| institution | Directory Open Access Journal |
| issn | 1681-6900 2412-0758 |
| language | English |
| last_indexed | 2024-03-08T06:06:11Z |
| publishDate | 2005-06-01 |
| publisher | Unviversity of Technology- Iraq |
| record_format | Article |
| series | Engineering and Technology Journal |
| spelling | doaj.art-f9c8b15d41d645f780d435531f6dd05d2024-02-04T17:55:49ZengUnviversity of Technology- IraqEngineering and Technology Journal1681-69002412-07582005-06-0124673474910.30684/etj.24.6.10182141Maximal Planarization of Non - Planar GraphsSuzan Yacob0Dept of Electrical Engineering, University of Technology, Baghdad-IRAQ.Abstract This paper presents a MAXIMAL - PLANARIZE algorithm using EQUIVELANT - GRAPH procedure . The algorithm proceeds by embedding one or few edges at each stage , without creating nonplanarity of the resultant graph , and to construct a maximal planar subgraph G , of G directly . The present implementation shows that using two planarization algorithms is unnecessary because of their complexities . It runs in linear time to give a maximal planar subgraph and adds the maximum number of edges possible without creating nonplanarity , using only one simple and efficient algorithm .https://etj.uotechnology.edu.iq/article_182141_b3338db9e790682d3a8f812082b5bcd6.pdfkey words: nonplanar graphhamiltonian circuit |
| spellingShingle | Suzan Yacob Maximal Planarization of Non - Planar Graphs Engineering and Technology Journal key words: nonplanar graph hamiltonian circuit |
| title | Maximal Planarization of Non - Planar Graphs |
| title_full | Maximal Planarization of Non - Planar Graphs |
| title_fullStr | Maximal Planarization of Non - Planar Graphs |
| title_full_unstemmed | Maximal Planarization of Non - Planar Graphs |
| title_short | Maximal Planarization of Non - Planar Graphs |
| title_sort | maximal planarization of non planar graphs |
| topic | key words: nonplanar graph hamiltonian circuit |
| url | https://etj.uotechnology.edu.iq/article_182141_b3338db9e790682d3a8f812082b5bcd6.pdf |
| work_keys_str_mv | AT suzanyacob maximalplanarizationofnonplanargraphs |