A separator-based method for 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. In the next and final step, we insert additional edges to giv...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-05
Main Authors: Rahman, Md Zamilur, Mukhopadhyay, Asish, Aneja, Yash P
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph theory
Insertion
Separators
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. In the next and final step, we insert additional edges to give us a weakly chordal graph on 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(n^3) time and an insertion takes constant time. On the other hand, a generation algorithm based on finding a 2-pair takes O(nm) time using the algorithm of Arikati and Rangan [1].
ISSN:2331-8422