On some properties of doughnut graphs
The class of doughnut graphs is a subclass of 5-connected planar graphs. It is known that a doughnut graph admits a straight-line grid drawing with linear area, the outerplanarity of a doughnut graph is 3, and a doughnut graph is k-partitionable. In this paper we show that a doughnut graph exhibits...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2016-08-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S0972860016300895 |
| _version_ | 1818760397432291328 |
|---|---|
| author | Md. Rezaul Karim Md. Jawaherul Alam Md. Saidur Rahman |
| author_facet | Md. Rezaul Karim Md. Jawaherul Alam Md. Saidur Rahman |
| author_sort | Md. Rezaul Karim |
| collection | DOAJ |
| description | The class of doughnut graphs is a subclass of 5-connected planar graphs. It is known that a doughnut graph admits a straight-line grid drawing with linear area, the outerplanarity of a doughnut graph is 3, and a doughnut graph is k-partitionable. In this paper we show that a doughnut graph exhibits a recursive structure. We also give an efficient algorithm for finding a shortest path between any pair of vertices in a doughnut graph. We also propose a nice application of a doughnut graph based on its properties. |
| first_indexed | 2024-12-18T06:57:58Z |
| format | Article |
| id | doaj.art-2730facfd18849be9870b6ea481746d7 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 |
| language | English |
| last_indexed | 2024-12-18T06:57:58Z |
| publishDate | 2016-08-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-2730facfd18849be9870b6ea481746d72022-12-21T21:17:07ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002016-08-0113213013910.1016/j.akcej.2016.06.006On some properties of doughnut graphsMd. Rezaul Karim0Md. Jawaherul Alam1Md. Saidur Rahman2Department of Computer Science and Engineering, University of Dhaka, Dhaka-1000, BangladeshDepartment of Computer Science and Engineering, Bangladesh University of Engineering and Technology(BUET), Dhaka-1000, BangladeshDepartment of Computer Science and Engineering, Bangladesh University of Engineering and Technology(BUET), Dhaka-1000, BangladeshThe class of doughnut graphs is a subclass of 5-connected planar graphs. It is known that a doughnut graph admits a straight-line grid drawing with linear area, the outerplanarity of a doughnut graph is 3, and a doughnut graph is k-partitionable. In this paper we show that a doughnut graph exhibits a recursive structure. We also give an efficient algorithm for finding a shortest path between any pair of vertices in a doughnut graph. We also propose a nice application of a doughnut graph based on its properties.http://www.sciencedirect.com/science/article/pii/S0972860016300895Planar graphsRecursive structureHamiltonianFault toleranceConnectivity |
| spellingShingle | Md. Rezaul Karim Md. Jawaherul Alam Md. Saidur Rahman On some properties of doughnut graphs AKCE International Journal of Graphs and Combinatorics Planar graphs Recursive structure Hamiltonian Fault tolerance Connectivity |
| title | On some properties of doughnut graphs |
| title_full | On some properties of doughnut graphs |
| title_fullStr | On some properties of doughnut graphs |
| title_full_unstemmed | On some properties of doughnut graphs |
| title_short | On some properties of doughnut graphs |
| title_sort | on some properties of doughnut graphs |
| topic | Planar graphs Recursive structure Hamiltonian Fault tolerance Connectivity |
| url | http://www.sciencedirect.com/science/article/pii/S0972860016300895 |
| work_keys_str_mv | AT mdrezaulkarim onsomepropertiesofdoughnutgraphs AT mdjawaherulalam onsomepropertiesofdoughnutgraphs AT mdsaidurrahman onsomepropertiesofdoughnutgraphs |