Gray coding cubic planar maps

Sergey Avgustinovich, Sergey Kitaev, Vladimir Potapov, Vincent Vajnovszki

Research output: Contribution to journalArticle

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.
LanguageEnglish
Pages59-69
Number of pages11
JournalTheoretical Computer Science
Volume616
Early online date22 Dec 2015
DOIs
Publication statusPublished - 22 Feb 2016

Fingerprint

Planar Maps
Coding
Gray Code
Nonseparable

Keywords

  • planar map
  • bicubic planar map
  • cubic non-separable planar map
  • 3-connected cubic planar map
  • gray code
  • description tree
  • β(0,1)-tree

Cite this

Avgustinovich, Sergey ; Kitaev, Sergey ; Potapov, Vladimir ; Vajnovszki, Vincent. / Gray coding cubic planar maps. In: Theoretical Computer Science. 2016 ; Vol. 616. pp. 59-69.
@article{025fb5854d8c4e98a5a902e60e92f9bf,
title = "Gray coding cubic planar maps",
abstract = "The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objectsdiffer 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.",
keywords = "planar map, bicubic planar map, cubic non-separable planar map, 3-connected cubic planar map, gray code, description tree , β(0,1)-tree",
author = "Sergey Avgustinovich and Sergey Kitaev and Vladimir Potapov and Vincent Vajnovszki",
year = "2016",
month = "2",
day = "22",
doi = "10.1016/j.tcs.2015.12.013",
language = "English",
volume = "616",
pages = "59--69",
journal = "Theoretical Computer Science",
issn = "0304-3975",

}

Avgustinovich, S, Kitaev, S, Potapov, V & Vajnovszki, V 2016, 'Gray coding cubic planar maps' Theoretical Computer Science, vol. 616, pp. 59-69. https://doi.org/10.1016/j.tcs.2015.12.013

Gray coding cubic planar maps. / Avgustinovich, Sergey; Kitaev, Sergey; Potapov, Vladimir; Vajnovszki, Vincent.

In: Theoretical Computer Science, Vol. 616, 22.02.2016, p. 59-69.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Gray coding cubic planar maps

AU - Avgustinovich, Sergey

AU - Kitaev, Sergey

AU - Potapov, Vladimir

AU - Vajnovszki, Vincent

PY - 2016/2/22

Y1 - 2016/2/22

N2 - The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objectsdiffer 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.

AB - The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objectsdiffer 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.

KW - planar map

KW - bicubic planar map

KW - cubic non-separable planar map

KW - 3-connected cubic planar map

KW - gray code

KW - description tree

KW - β(0,1)-tree

UR - http://www.sciencedirect.com/science/article/pii/S0304397515011743

U2 - 10.1016/j.tcs.2015.12.013

DO - 10.1016/j.tcs.2015.12.013

M3 - Article

VL - 616

SP - 59

EP - 69

JO - Theoretical Computer Science

T2 - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -