Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs

• ZHUANG Bingbing

  Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University

• NAGAMOCHI Hiroshi

  Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University

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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E94-D (2), 200-210, 2011

  The Institute of Electronics, Information and Communication Engineers

Keywords

• enumeration
• reflective symmetry
• triangulation
• plane graphs
• planar graphs
• biconnectivity
• graph algorithms

Details

• CRID: 1390282679355086976
• NII Article ID: 130000453880
• DOI: 10.1587/transinf.e94.d.200
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E94.D/2/E94.D_2_200/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed