Journal of Algorithms 30, pp. 344--378 (1999).

Fast algorithms for K4 immersion testing

Heather D. Booth, Rajeev Govindan, Michael A. Langston and Siddharthan Ramachandramurthi

Abstract

Many useful classes of graphs can in principle be recognized with finite batteries of obstruction tests. One of the most fundamental tests is to determine whether an arbitrary input graph contains K4 in the immersion order. In this paper, we present for the first time a fast, practical algorithm to accomplish this task. We also extend our method so that, should an immersed K4 be present, a K4 model is isolated.


Siddharthan Ramachandramurthi --