In the game of Kal-toh depicted in the television series Star Trek: Voyager, players
attempt to create polyhedra by adding to a jumbled collection of metal rods. Inspired by
this fictional game, we formulate graph-theoretical questions about polyhedral (triconnected and planar) subgraphs in an on-line environment. The problem of determining the existence of a polyhedral subgraph within a graph G is shown to be NP-hard, and we also give some non-trivial upper bounds for the problem of determining the minimum number of edge additions necessary to guarantee the existence of a polyhedral subgraph in G. A two-player
formulation of Kal-toh is also explored, in which the first player to form a target subgraph is declared the winner. We show a polynomial-time solution for simple cases of this game but conjecture that the general problem is NP-hard.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5882 |
| Date | 21 April 2011 |
| Creators | Anderson, Terry David |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0014 seconds