Generating Biconnected Plane Quadrangulations

  • LI Zhang-Jian
    the Department of Computer Science, Faculty of Engineering, Gunma University
  • NAKANO Shin-ichi
    the Department of Computer Science, Faculty of Engineering, Gunma University

Search this article

Description

A plane quadrangulation is a plane graph such that each inner face has exactly four edges on its contour. This is a planar dual of a plane graph such that all inner vertices have degree exactly four. A based plane quadrangulation is a plane quadrangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane quadrangulations with at most f faces. The algorithm uses O(f) space and generates such quadrangulations in O(1) time per quadrangulation without duplications. By modifying the algorithm we can generate all biconnected (non-based) plane quadrangulations with at most f faces in O(f^3) time per quadrangulation.

Journal

References(8)*help

See more

Details 詳細情報について

  • CRID
    1573950402084213760
  • NII Article ID
    110003223268
  • NII Book ID
    AA10826272
  • ISSN
    09168532
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top