Gray coding cubic planar maps

DOI10.1016/J.TCS.2015.12.013MaRDI QIDQ906395zbMATH OpenOpenAlexFDO

Authors Sergey Kitaev, Sergey Avgustinovich, Vladimir N. Potapov, Vincent Vajnovszki

Publication date 21 January 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.05807

zbMATH Keywords

Gray codeplanar map\(\beta(0, 1)\)-tree3-connected cubic planar mapbicubic planar mapcubic non-separable planar mapdescription tree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial codes (94B25)

Abstract: The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objects differ in some pre-specified small way. In this paper, we utilize beta-description trees to cyclicly Gray code three classes of cubic planar maps, namely, bicubic planar maps, 3-connected cubic planar maps, and cubic non-separable planar maps.

Recommendations

• Gray code enumeration of plane straight-line graphs
• A Survey of Combinatorial Gray Codes
• Gray code numbers for graphs
• scientific article; zbMATH DE number 706769
• On combinatorial Gray codes with distance 3

Cites work

• scientific article; zbMATH DE number 1151365 (Why is no real title available?)
• scientific article; zbMATH DE number 2040940 (Why is no real title available?)
• A Census of Planar Maps
• A Survey of Combinatorial Gray Codes
• An involution on bicubic maps and \beta(0,1)-trees
• Combinatorial Gray codes for classes of pattern avoiding permutations
• Description trees and Tutte formulas.
• Generating a Gray code for P-sequences
• Generating binary trees by transpositions
• On the hamiltonicity of the Cartesian product

Cited in

(3)

• Gray code enumeration of plane straight-line graphs
• Combinatorial generation via permutation languages. I: Fundamentals
• Combinatorial Gray codes -- an updated survey

This page was built for publication: Gray coding cubic planar maps

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