Left Right Planarity testing and Maximal planar subgraph

dc.contributor.advisor Stephens, Chis
dc.contributor.author Gurgil, Ibrahim
dc.contributor.committeemember Ye, Dong
dc.contributor.committeemember Zha, Xiaoya
dc.contributor.committeemember Seo, Suk Jai
dc.date.accessioned 2020-02-03T13:10:43Z
dc.date.available 2020-02-03T13:10:43Z
dc.date.issued 2020
dc.date.updated 2020-02-03T13:10:45Z
dc.description.abstract According to our best knowledge, the Left-Right algorithm offers the fastest speed for planarity testing. We show that in finding the Kuratowski K_5 graph, the Left-Right algorithm fails in some cases. We have revised the Left-Right algorithm for the Kuratowski graph with 5 vertices. We further added some features to the Left-Right algorithm to extract the Kuratowski subgraphs. We will discuss the additions to the Left-Right approach and its possible usages. It is proven that Left-Right (LR) approach is one of the fastest algorithms to find if a graph is planar. We updated the algorithm of LR to extract the Kuratowski subgraphs efficiently. A maximal planar subgraph (G’) of G is a graph with the same vertex set of G and with a minimal set of missing edges from G such that if any removed edge is added to G', the graph becomes non-planar again. If G is planar, then the maximum (maximal) planar subgraph is itself. Otherwise we will discuss how to find the minimum set of edges to be removed to make a graph planar using the updated LR approach.
dc.description.degree Ph.D.
dc.identifier.uri https://jewlscholar.mtsu.edu/handle/mtsu/6136
dc.language.rfc3066 en
dc.publisher Middle Tennessee State University
dc.subject Applied mathematics
dc.subject Mathematics
dc.thesis.degreegrantor Middle Tennessee State University
dc.thesis.degreelevel doctoral
dc.title Left Right Planarity testing and Maximal planar subgraph
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
504.79 KB
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
0 B
Item-specific license agreed upon to submission