Heegaard splittings with boundary and almost normal surfaces

This paper generalizes the definition of a Heegaard splitting to unify the concepts of thin position for 3-manifolds [M. Scharlemann, A. Thompson, Contemp. Math., Vol. 164, Amer. Math. Soc., 1994, pp. 231–238], thin position for knots [D. Gabai, J. Differential Geom. 26 (1987) 479–536], and normal and almost normal surface theory [W. Haken, Acta Math. 105 (1961) 245–375]; [J.H. Rubinstein, Proc. Georgia Topology Conference, 1995, pp. 1–20]. This gives generalizations of theorems of Scharlemann, Thompson, Rubinstein, and Stocking. In the final section, we use this machinery to produce an algorithm to determine the bridge number of a knot, provided thin position for the knot coincides with bridge position. We also present several algorithmic and finiteness results about Dehn fillings with small Heegaard genus.