LexBFS: a powerful algorithm for any graph
 
 
 

Abstract:

  We are the first to show that LexBFS, a linear algorithm for the recognition of triangulated graphs, is based on a powerful invariant which is true for any graph (whether triangulated or not).
  Our invariant uses separability considerations. Since minimal separators play an important role in triangulated graphs, it is not surprising that LexBFS follows their structure on general graphs. We explain the connection between the two, and how a triangulated graph can be seen as the backbone of a graph, by way of its minimal triangulation.
  This invariant yields an interesting  general theorem on graphs, generalizing the well-known notion that "every non-clique tree has at least two leaves": in a certain sense, we define the extremities of a graph, in the same way that leaves are the extremities of a tree.  We briefly address some of the corollaries; this theorem can be used theoretically in a much larger context than that offered by LexBFS, because, although this algorithm always finds an extremity (in fact two non-adjacent ones with a double pass), there are some extremities that it is not capable of finding.  Complexity-wise, LexBFS offers a linear access.
  We also derive a new characterization of both triangulated graphs and minimal triangulation, suggesting  an  opening to lower the current O(nm)-time complexity for minimal triangulation of a graph by using LexBFS directly in an iterative fashion.
  As an illustration, we explain how LexBFS can be used to make Tarjan's decomposition by clique separators into a unique decomposition with no extra cost.