Memory efficient algorithms for cactus graphs and block graphs

We present constant-work-space polynomial time algorithms for solving the shortest path problem, finding the chromatic polynomial, clique number, number of components, circumference, and girth of cactus graphs and block graphs. For some of these problems we also present in-place algorithms, which perform faster than the corresponding constant-work-space algorithms. The problems considered are fundamental to many areas of graph theory, computational geometry, and combinatorial optimization, and have a wide range of applications including transportation, robotics, and image processing.