Return to search

The Vulcan game of Kal-toh: Finding or making triconnected planar subgraphs

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.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/5882
Date21 April 2011
CreatorsAnderson, Terry David
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0016 seconds