Embedding a Planar Graph on a Given Point Set
| dc.contributor.author | MONDAL, DEBAJYOTI | |
| dc.contributor.examiningcommittee | Gethner, Ellen (Computer Science, University of Colorado Denver) Domaratzki, Michael (Computer Science) | en_US |
| dc.contributor.supervisor | Durocher, Stephane (Computer Science) | en_US |
| dc.date.accessioned | 2012-09-18T16:54:44Z | |
| dc.date.available | 2012-09-18T16:54:44Z | |
| dc.date.issued | 2012-02 | en_US |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| dc.description.abstract | A point-set embedding of a planar graph G with n vertices on a set S of n points is a planar straight-line drawing of G, where each vertex of G is mapped to a distinct point of S. We prove that the point-set embeddability problem is NP-complete for 3-connected planar graphs, answering a question of Cabello [20]. We give an O(nlog^3n)-time algorithm for testing point-set embeddability of plane 3-trees, improving the algorithm of Moosa and Rahman [60]. We prove that no set of 24 points can support all planar 3-trees with 24 vertices, partially answering a question of Kobourov [55]. We compute 2-bend point-set embeddings of plane 3-trees in O(W^2) area, where W is the length of longest edge of the bounding box of S. Finally, we design algorithms for testing convex point-set embeddability of klee graphs and arbitrary planar graphs. | en_US |
| dc.description.note | October 2012 | en_US |
| dc.identifier.citation | In Proceedings of the 6th International Workshop on Algorithms and Computation (WALCOM 2012), LNCS, 7157, Springer, pp. 148-159, February 2012 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/8869 | |
| dc.language.iso | eng | en_US |
| dc.publisher | Springer-Verlag Berlin | en_US |
| dc.rights | open access | en_US |
| dc.subject | Graph Drawing | en_US |
| dc.subject | Point-Set Embedding | en_US |
| dc.title | Embedding a Planar Graph on a Given Point Set | en_US |
| dc.type | master thesis | en_US |