IEICE TRANSACTIONS on Information
Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
Summary :
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
