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." />
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs

Bingbing ZHUANG
Hiroshi NAGAMOCHI

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D    No.2    pp.200-210
Publication Date: 2011/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.200
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
enumeration,  reflective symmetry,  triangulation,  plane graphs,  planar graphs,  biconnectivity,  graph algorithms,  

Full Text: PDF(886.5KB)>>
Buy this Article


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.

open access publishing via