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

triconnectivity;planarity;polyhedra;subgraphs;Computer Science

Anderson, Terry David

University of Waterloo

关键词: triconnectivity;    planarity;    polyhedra;    subgraphs;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/5882/1/Anderson_Terry.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In the game of Kal-toh depicted in the television series Star Trek: Voyager, playersattempt to create polyhedra by adding to a jumbled collection of metal rods. Inspired bythis 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-playerformulation 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.