Md Zamilur Rahman

 

Date: Friday, November 15, 2019

Time: 10:00am

Location: Essex Hall Room 109

 

A graph G is chordal if it has no chordless cycles of size four or more. However, the complement of a chordal graph G can contain an induced chordless cycle of size four. The complement cannot contain a five cycle, as the complement of a five cycle is also a five cycle. This suggests the generalization of chordal graphs to weakly chordal (or weakly triangulated) graphs as those graphs G such that neither G nor its complement G¯ contains induced chordless cycles of size five or greater. From the symmetry of the definition it follows that G¯ is also weakly chordal. The problem of generating graphs uniformly at random has received much attention but little is known about the problem of generating weakly chordal graphs. There are many situations (such as generating all linear layouts of weakly chordal graphs) where we want to generate instances of these to test algorithms for weakly chordal graphs. In this talk we address the algorithmic problem of generating weakly chordal graphs. 

We propose a scheme for generating a weakly chordal graph on n vertices with m edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a weakly chordal graph on the n vertices) based on this tree. We then insert additional edges, if needed, for a total of m edges. Our algorithm ensures that the graph remains weakly chordal after each edge is inserted. The time complexity of an insertion query is O(du2dv2(n+m)), where du and dv are the degrees of the vertices u and v we want to join with an edge and an insertion takes constant time. The advantages of this method are that it uses very simple data structures and exploits the basic structural properties of a weakly chordal graph.

Thesis Committee: 

 

PhD Seminar Announcement