On the succinct representation of graphs

DOI10.1016/0166-218X(84)90126-4zbMath0551.68059WikidataQ56209828 ScholiaQ56209828MaRDI QIDQ800734

György Turán

Publication date: 1984

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

zbMATH Keywords

planar graphsencoding of graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (27)

Linearity is strictly more powerful than contiguity for encoding graphs ⋮ Schnyder woods for higher genus triangulated surfaces, with applications to encoding ⋮ Trading uninitialized space for time ⋮ Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs ⋮ Graph compression by BFS ⋮ Succinct encoding of binary strings representing triangulations ⋮ Succinct encoding of arbitrary graphs ⋮ (Nearly-)tight bounds on the contiguity and linearity of cographs ⋮ Simple planar graph partition into three forests ⋮ Compact representations of spatial hierarchical structures with support for topological queries ⋮ A compact encoding of plane triangulations with efficient query supports ⋮ The saga of minimum spanning trees ⋮ Succinct Representations of Arbitrary Graphs ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Succinct representations of planar maps ⋮ Representing graphs implicitly using almost optimal space ⋮ Quick encoding of plane graphs in \(\log _{2}14\) bits per edge ⋮ Planar graphs, via well-orderly maps and trees ⋮ An edgebreaker-based efficient compression scheme for regular meshes ⋮ Succinct representation of general unlabeled graphs ⋮ A Compact Encoding of Plane Triangulations with Efficient Query Supports ⋮ Asymptotic enumeration and limit laws of planar graphs ⋮ Fast and compact planar embeddings ⋮ Short encodings of planar graphs and maps ⋮ A Census of Plane Graphs with Polyline Edges ⋮ Navigating planar topologies in near-optimal space and time ⋮ Finite presentation of homogeneous graphs, posets and Ramsey classes

Cites Work

• The complexity of computing the permanent
• Representation of graphs
• Sur la rationalite de certaines séries generatrices
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the succinct representation of graphs