Abstract: The problem of finding sparse underlying subgraphs, which also maintain the distance information between any 2 pair of vertices, is an important one in graph theory, with several applications. One approach would be to find tree $t$-spanners, i.e., spanning trees in which the distance between any pair of vertices is atmost $t$ times their distance in the original graph $(t>=1)$. The tree $t$ spanner problem has been shown to be NP-complete, when $t$ is part of the input, for general graphs. In this talk, we will study an algorithm which solves the tree $t$ spanner problem in 2-connected outerplanar graphs, in $O(n)$ time ($n$ is the number of vertices).
A familiarity with the basic concepts of graph theory is desirable.
School of Mathematical Sciences
NISER, PO- Bhimpur-Padanpur, Via- Jatni, District- Khurda, Odisha, India, PIN- 752050