Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
Summary :
In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.
- Publication
- IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.200-210
- Publication Date
- 2011/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E94.D.200
- 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 Triangulated Planar Graphs" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 200-210, February 2011, doi: 10.1587/transinf.E94.D.200.
Abstract: In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.200/_p
Copy
@ARTICLE{e94-d_2_200,
author={Bingbing ZHUANG, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs},
year={2011},
volume={E94-D},
number={2},
pages={200-210},
abstract={In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.},
keywords={},
doi={10.1587/transinf.E94.D.200},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 200
EP - 210
AU - Bingbing ZHUANG
AU - Hiroshi NAGAMOCHI
PY - 2011
DO - 10.1587/transinf.E94.D.200
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 triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.
ER -
English
