Compact Encodings of Graphs with Efficient Query Support

点击翻译按钮获取中文摘要

A rectangular drawing is a plane drawing in which every face is a rectangle. We have designed a simple encoding scheme for rectangular drawings as follows. Given a rectangular drawing R with maximum degree 3, our scheme encodes R with 5m/3 + o (n) bits for each n-vertex rectangular drawing R, where m is the number of edges of R, and supports a rich set of queries, including adjacency and degree queries on the faces, in constant time.Also we have designed efficient enumeration algorithms for 4 connected maximal plane graphs, and connected plane graphs, in which we have designed a compact coding for each class of graphs.