External-memory graph algorithms

We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a 2/3-separator of size 2 for a given outerplanar graph. Our ...

Given a graph G = ( V , E ) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique ...