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
BOOTH, KS
LUEKER, GS
[J]. 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
HOPCROFT, J
TARJAN, R
[J]. JOURNAL OF THE ACM, 1974, 21 (04) : 549 - 568
[5] REPRESENTATION OF GRAPHS
ITAI, A
RODEH, M
[J]. ACTA INFORMATICA, 1982, 17 (02) : 215 - 219
[6] JACOBSON G, 1989, 30TH P IEEE S F COMP
[7] SUCCINCT REPRESENTATION OF GENERAL UNLABELED GRAPHS
NAOR, M
[J]. 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
TURAN, G
[J]. DISCRETE APPLIED MATHEMATICS, 1984, 8 (03) : 289 - 294
[10] A CENSUS OF PLANAR TRIANGULATIONS
TUTTE, WT
[J]. CANADIAN JOURNAL OF MATHEMATICS, 1962, 14 (01): : 21 - &

← 1 2 →