4連結極大平面グラフの列挙(理論)

• 高埜 博典

  群馬大学工学部情報工学科

• 中野 眞一

  群馬大学工学部情報工学科

書誌事項

タイトル別名

• Generating 4-connected plane triangulations(Theory)
• 4連結極大平面グラフの列挙
• 4 レンケツ キョクダイ ヘイメン グラフ ノ レッキョ

抄録

A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all 4-connected based plane triangulations with at most n vertices. This is the first algorithm to generate such triangulations. The algorithm uses O(n) space and generates such triangulations in O(n) time per triangulation without duplications. By modifying the algorithm one can generate all 4-connected (non-based) plane triangulations with at most n vertices in O(n^2) time per triangulation without duplications.

収録刊行物

• 日本応用数理学会論文誌

  日本応用数理学会論文誌 17 (4), 363-397, 2007

  一般社団法人 日本応用数理学会

詳細情報

• CRID: 1390282680744516736
• NII論文ID: 110006532076
• NII書誌ID: AN10367166
• ISSN: 09172246
• ISSN: 24240982
• DOI: 10.11540/jsiamt.17.4_363
• NDL書誌ID: 9333199
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I9333199
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可