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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:MWU.1993/8869 |
| Date | 02 1900 |
| Creators | MONDAL, DEBAJYOTI |
| Contributors | Durocher, Stephane (Computer Science), Gethner, Ellen (Computer Science, University of Colorado Denver) Domaratzki, Michael (Computer Science) |
| Publisher | Springer-Verlag Berlin |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Detected Language | English |
Page generated in 0.0015 seconds