SHORT ENCODINGS OF PLANAR GRAPHS AND MAPS

被引：63

作者：

KEELER, K

WESTBROOK, J

机构：

[1] YALE UNIV, DEPT COMP SCI, NEW HAVEN, CT 06520 USA

[2] AT&T BELL LABS, DEPT PERFORMANCE ANAL, NAPERVILLE, IL 60566 USA

[3] HARVARD UNIV, DIV APPL SCI, CAMBRIDGE, MA 02138 USA

来源：

DISCRETE APPLIED MATHEMATICS | 1995年 / 58卷 / 03期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0166-218X(93)E0150-W

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We discuss space-efficient encoding schemes for planar graphs and maps. Our results improve on the constants of previous schemes and can be achieved with simple encoding algorithms. They are near-optimal in number of bits per edge.

引用

页码：239 / 252

页数：14

共 11 条

[1] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

[2]

ELIAS P, 1975, IEEE T INFORM THEORY, V21, P194, DOI 10.1109/TIT.1975.1055349

[3]

Harary Frank, 1972, GRAPH THEORY

[4] EFFICIENT PLANARITY TESTING [J].

HOPCROFT, J ;

TARJAN, R .

JOURNAL OF THE ACM, 1974, 21 (04) :549-568

[5] REPRESENTATION OF GRAPHS [J].

ITAI, A ;

RODEH, M .

ACTA INFORMATICA, 1982, 17 (02) :215-219

[6]

JACOBSON G, 1989, 30TH P IEEE S F COMP

[7] SUCCINCT REPRESENTATION OF GENERAL UNLABELED GRAPHS [J].

NAOR, M .

DISCRETE APPLIED MATHEMATICS, 1990, 28 (03) :303-307

[8]

Tarjan R., 1972, SIAM Journal on Computing, V1, P146, DOI 10.1137/0201010

[9] ON THE SUCCINCT REPRESENTATION OF GRAPHS [J].

TURAN, G .

DISCRETE APPLIED MATHEMATICS, 1984, 8 (03) :289-294

[10] A CENSUS OF PLANAR TRIANGULATIONS [J].

TUTTE, WT .

CANADIAN JOURNAL OF MATHEMATICS, 1962, 14 (01) :21-&

← 1 2 →