Date: Friday May 15th, 2020

 

Time:  1:00pm – 2:30pm

 

Zoom meeting url: https://zoom.us/j/95185509764?

 

 

Graph theory is an important field of study that enables one to get general ideas about graphs and their properties. It helps supply numerical information for enumerative problems and to provide a source from which specimen graphs can be taken for use in real-life problems. 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 my thesis we address the algorithmic problem of generating weakly chordal graphs. A graph G=(V, E), where V is the set of its vertices and E is the set of its edges, is called weakly chordal graph, if neither G, nor its complement G’, contains an induced chordless cycle on five or more vertices.

 

Our work is in two parts. In the first part, we carry out a comparative study of two existing algorithms for generating weakly chordal graphs. A pair {u,v} of non-adjacent vertices in G form a two-pair if every chordless path between u and v is of length two. The first algorithm for generating weakly chordal graphs, repeatedly finds a two-pair and adds an edge between them. The second generation algorithm starts by constructing a tree and then generates an orthogonal layout (which is a weakly chordal graph on the n vertices) based on this tree. Edges are then inserted into this orthogonal layout till there are m edges. The output graphs from these two methods are compared with respect to several parameters like number of four cycles, the number of non two-pairs in the graphs generated by the second method.

 

In the second part, we propose an algorithm for generating weakly chordal graphs by edge deletions starting from an arbitrary input random graph. The algorithm starts with an arbitrary graph as an input to be able to generate a weakly chordal graph by the basis of edge deletion. The algorithm iterates by maintaining weak chordality by preventing no hole or antihole configurations being formed for any successful deletion of an edge.

 

Keywords: Weakly Chordal Graph, Two-Pair, Hole, Anti-Hole, Generation Algorithm

 

 

 

Internal Reader: Dr. Dan Wu      

 

External Reader: Dr. Yash Aneja

 

Advisor: Dr. Asish Mukhopadhyay

 

Chair:    Dr. Jessica Chen