Practical encodings of graphs with highly functional query supports

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

We designed encoding algorithms of graphs. We mainly focuses on plane triangulations and grid rectangular drawing, and developed encoding algorithms of them. The algorithm can encode a plane triangulation with compact space and supports the following queries : (1) adjacency, (2) degree, and (3) clockwise neighbour query. The clockwise neighbor query is frequently used in algorithms for plane graphs. Hence it is an extremely practical query. We also developed an algorithm which encodes a grid rectangular drawing with compact space.