Cubic graphs
Raymond Greenlaw, Rossella Petreschi · ACM Computing Surveys · 1995
This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphs and their history. Several classical graph theory results concerning cubic graphs are explained. Graph theory problems whose solutions on cubic graphs are particularly important or interesting are presented both from the sequential and parallel point of view. A new algorithm is presented for the maximal matching problem restricted to cubic graphs. Many miscellaneous facts about cubic graphs are also described. An extensive list of references is provided.