# MSc Thesis Proposal Announcement by Sudiksha Khanduja:"Weakly chordal graphs: An Experimental Study "

Wednesday, January 22, 2020 - 11:00 to 13:00

# SCHOOL OF COMPUTER SCIENCE

## MSc Thesis Proposal by: Sudiksha Khanduja

Date: January 22, 2020

Time:  11 am – 1 pm

Location: Lambton Tower, Room 3105

## Abstract:

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 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 nonadjacent vertices in G form a 2-pair if every chordless path between u and v is of length two. The first algorithm for generating weakly chordal graphs, repeatedly finds a 2-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 2-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 from a complete graph. The algorithm starts with a complete graph to generate a weakly chordal graph. The algorithm iterates by preventing a hole or an antihole configuration being created for every successful deletion of an edge.