OBDD Representation of Intersection Graphs

Asahi TAKAOKA  Satoshi TAYU  Shuichi UENO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.4   pp.824-834
Publication Date: 2015/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7281
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
implicit representation of graphs,  ordered binary decision diagrams,  orthogonal ray graphs,  permutation graphs,  

Full Text: PDF(426.3KB)
>>Buy this Article


Summary: 
Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.