Speaker:  Jit Bose, Carleton University
Time:     Wednesday, January 23, 1:30 p.m.
Place:    HP4369 School of Math and Stats, Carleton University
Title:    Worst-Case-Optimal Algorithms for Guard/Utility Placement on
          Polyhedral Surfaces

abstract:
We present an optimal $\Theta(n)$-time algorithm for the selection 
of a subset of the vertices of an $n$-vertex plane graph
$G$ so that each of the faces of $G$ is covered by (i.e. incident
with) one or more of the selected vertices.  At most $\lfloor n/2
\rfloor$ vertices are selected, matching the worst-case
requirement. Analogous results for edge-covers are developed for two
different notions of ``coverage''.  In particular, our linear-time
algorithm selects at most $n - 2$ edges to {\em strongly} cover $G$,
at most $\lfloor n/3 \rfloor$ diagonals to cover $G$, and in the case
where $G$ has no quadrilateral faces, at most $\lfloor n/3 \rfloor$
edges to cover $G$.  All these bounds match the worst-case
requirements.  Our algorithms apply directly to the location of
guards, utilities or illumination sources on the vertices or edges of
polyhedral surfaces or planar subdivisions.