Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

DOI10.1137/S0895480197325031MaRDI QIDQ4699160zbMATH OpenFDO

Authors Xin He, Hsueh-I Lu, Ming-Yang Kao

Publication date 23 November 1999

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480197325031

zbMATH Keywords

canonical orderingdata compressiongraph encodingplanar graphstriangulationstriconnected graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Short encodings of planar graphs and maps
• On the succinct representation of graphs
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• A compact encoding of plane triangulations with efficient query supports

Cited in

(16)

• Constructing compact rectilinear planar layouts using canonical representation of planar graphs
• Short encodings of planar graphs and maps
• Orderly spanning trees with applications to graph encoding and graph drawing
• Space-efficient planar acyclicity constraints. A declarative pearl
• Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights
• A compact encoding of plane triangulations with efficient query supports
• scientific article; zbMATH DE number 1974118 (Why is no real title available?)
• A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
• An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps
• A Compact Encoding of Plane Triangulations with Efficient Query Supports
• An edgebreaker-based efficient compression scheme for regular meshes
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• Visibility representations of four-connected plane graphs with near optimal heights
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Quick encoding of plane graphs in \(\log _{2}14\) bits per edge

This page was built for publication: Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699160)