ALGEBRAIC APPROACH TO FASCIAGRAPHS AND ROTAGRAPHS

An algebraic approach is proposed which can be used to solve different problems on fasciagraphs and rotagraphs. A particular instance of thi s method computes the domination number of fasciagraphs and rotagraphs in O(log n) time, where n is the number of monographs of such a graph . Fasciagraphs and rotagraphs include complete grid graphs P-k square P-n and graphs C-k square C-n. The best previously known algorithms fo r computing the domination number of P-k square P-n are of lime comple xity O(n) (for a fixed k).