Combinatorial reconstruction problems and width parameters of graphs
Dieter Rautenbach (RWTH-Aachen, Germany)

Abstract : I will present two of the topics that I have recently worked on: {\it Combinatorial reconstruction problems} and {\it width parameters of graphs}. While the first one is mainly focused on theoretical issues of Discrete Mathematics, the second one has a strong algorithmical motivation.

The basic question asked in reconstruction problems is whether certain information about the isomorphism types of the subobjects of an unknown object allows to reconstruct this object up to isomorphism. This kind of question has its origin in two famous open conjectures about finite graphs. In a first part of this talk I will consider reconstruction problems for subsets of ${\bf R}^n$ given up to isometries \cite{r1}. Among other results I will present a solution of a problem posed by Harary and Manvel in 1972 \cite{r2} and an answer to a question posed by Maynard in 1996.

The second part of this talk is devoted to the band-, tree- and clique-width of graphs \cite{lr}. All these width parameters measure the complexity of a graph as many NP-hard problems become solvable in polynomial time when restricted to graphs where one of these parameters is bounded. I will show how forbidding certain substructures in graphs of bounded vertex degree implies boundedness of these parameters. All results will be algorithmical in the sense that they lead to simple and efficient algorithms.

\begin{thebibliography}{9}
\bibitem{lr} V. Lozin and D. Rautenbach, The band-, tree- and clique-width of graphs of bounded vertex degree, RUTCOR preprint.
\bibitem{r1} D. Rautenbach, Reconstructing finite sets of points in ${\bf R}^n$ up to groups of isometries, {\it European Journal of Combinatorics} {\bf 22} (2001), 1139-1147.
\bibitem{r2} D. Rautenbach, On a reconstruction problem of Harary and Manvel, {\it J. Combin. Theory, Ser. A} {\bf 99} (2002), 32-39. \end{thebibliography} \end{document}

Announcement Poster in PDF