Short encodings of planar graphs and maps

DOI10.1016/0166-218X(93)E0150-WzbMath0833.05025OpenAlexW2010356699WikidataQ127570257 ScholiaQ127570257MaRDI QIDQ1805444

Kenneth Keeler, Jeffery Westbrook

Publication date: 11 March 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0150-w

zbMATH Keywords

mapsplanar graphsencodingdecoding algorithmsdepth-first search treelabels

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Related Items (19)

Schnyder woods for higher genus triangulated surfaces, with applications to encoding ⋮ The space complexity of sum labelling ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Succinct encoding of arbitrary graphs ⋮ Simple planar graph partition into three forests ⋮ A compact encoding of plane triangulations with efficient query supports ⋮ Succinct Representations of Arbitrary Graphs ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Succinct representations of planar maps ⋮ Linear-time compression of 2-manifold polygon meshes into information-theoretically optimal number of bits ⋮ Quick encoding of plane graphs in \(\log _{2}14\) bits per edge ⋮ The space complexity of sum labelling ⋮ Planar graphs, via well-orderly maps and trees ⋮ An edgebreaker-based efficient compression scheme for regular meshes ⋮ A Compact Encoding of Plane Triangulations with Efficient Query Supports ⋮ Fast and compact planar embeddings ⋮ On the OBDD size for graphs of bounded tree- and clique-width ⋮ BOUNDING THE NUMBER OF REDUCED TREES, COGRAPHS, AND SERIES-PARALLEL GRAPHS BY COMPRESSION ⋮ Navigating planar topologies in near-optimal space and time

Cites Work

• On the succinct representation of graphs
• Representation of graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Parallel concepts in graph theory
• Succinct representation of general unlabeled graphs
• A Census of Planar Triangulations
• Universal codeword sets and representations of the integers
• Efficient Planarity Testing
• Depth-First Search and Linear Graph Algorithms
• A Census of Planar Maps

This page was built for publication: Short encodings of planar graphs and maps