The search functionality is under construction.

The search functionality is under construction.

In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers *n* ≥ 3 and *g* ≥ 3, we give an *O*(*n*)-space and *O*(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly *n* vertices such that the size of each inner face is at most *g* without delivering two symmetric copies of the same graph.

- Publication
- IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.211-219

- Publication Date
- 2011/02/01

- Publicized

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.E94.D.211

- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Bingbing ZHUANG, Hiroshi NAGAMOCHI, "Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 211-219, February 2011, doi: 10.1587/transinf.E94.D.211.

Abstract: In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers *n* ≥ 3 and *g* ≥ 3, we give an *O*(*n*)-space and *O*(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly *n* vertices such that the size of each inner face is at most *g* without delivering two symmetric copies of the same graph.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.211/_p

Copy

@ARTICLE{e94-d_2_211,

author={Bingbing ZHUANG, Hiroshi NAGAMOCHI, },

journal={IEICE TRANSACTIONS on Information},

title={Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs},

year={2011},

volume={E94-D},

number={2},

pages={211-219},

abstract={In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers *n* ≥ 3 and *g* ≥ 3, we give an *O*(*n*)-space and *O*(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly *n* vertices such that the size of each inner face is at most *g* without delivering two symmetric copies of the same graph.},

keywords={},

doi={10.1587/transinf.E94.D.211},

ISSN={1745-1361},

month={February},}

Copy

TY - JOUR

TI - Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs

T2 - IEICE TRANSACTIONS on Information

SP - 211

EP - 219

AU - Bingbing ZHUANG

AU - Hiroshi NAGAMOCHI

PY - 2011

DO - 10.1587/transinf.E94.D.211

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E94-D

IS - 2

JA - IEICE TRANSACTIONS on Information

Y1 - February 2011

AB - In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers *n* ≥ 3 and *g* ≥ 3, we give an *O*(*n*)-space and *O*(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly *n* vertices such that the size of each inner face is at most *g* without delivering two symmetric copies of the same graph.

ER -