FU Berlin, Fachbereich Mathematik und Informatik, Institut für Informatik

Vortrag des Informatik-Kolloquiums 

Prof. Dr. Christian Knauer lädt ein:

 The Logic Engine and the Touching Graph of Spheres

Sue Whitesides, School of Computer Science, McGill-University

We review the ``logic engine'' approach for obtaining lower bound complexity results for certain questions concerning the layout, or geometric representation, of graphs. In particular, we consider the following graph recognition problem: Given a graph G, is it possible to map its vertices to points in 3D such that G is isomorphic to the touching graph of unit spheres centered at those points? We show that this problem is NP-hard. We do this by extending the logic engine method to three dimensions by using building blocks inpired by the structure of diamond and by constructions of Alexander Graham Bell and Buckminster Fuller. Joint work with Matthew Kitching.

  Ort: Takustr. 9, Raum 049,  Zeit: Fr, 6.5.2005, 14 Uhr  c.t.
  Kaffee um 13:45 im Raum 134 (Institutsküche)