Campus Event Calendar
Event Entry
What and Who
SPQR-Trees and planar embeddings
Rene Weiskircher
Max-Planck-Institut für Max-Planck-Institut für Informatik, Saarbrücken, Germany
Seminar des Graduiertenkollegs
AG 1, AG 2
AG Audience
-- Not specified --
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 20 July 98
16:00
60 Minutes
Geb. 45
016
Saarbrücken
Abstract
An SPQR-tree of a biconnected planar graph G represents a recursive decomposition of G with respect to its split pairs. It can be used to represent all planarembeddings of G. First I will give a short introduction to SPQR-trees and andshow how to construct them. Then I will demonstrate how this data-structure canbe used to represent all embeddings of a graph. In the second half of the talk,I will introduce an integer linear program that is based on the decomposition represented by the SPQR-tree with the property that the set of solutions represents exactly the set of all planar embeddings of the graph.
Contact
Ülkü Coruh
9325 - 526
--email hidden
passcode not visible
logged in users only