一般化ドーナツグラフの格子直線描画

DOI

書誌事項

タイトル別名
  • Straight-Line Grid Drawings of Generalized Doughnut Graphs

この論文をさがす

説明

平面グラフGの各点が整数格子の格子点上に配置され，Gの各辺が互いに交差しない直線分として描かれる描画をGの格子直線描画という．任意の平面グラフGは(n-2)×(n-2)の大きさの整数格子内に格子直線描画できることが知られている [15]．ここでnはGの点数である．一方，入力グラフにある種の制約があるならば，より小さな面積の格子内に格子直線描画できることが予想される．本論文では，まず5連結p-k重ドーナツグラフGの定義を与える．更に，5連結p-k重ドーナツグラフGは，n/(2k-2)+(2k-5) × (2k-1)，すなわちO(n)の面積の整数格子内に格子直線描画かつ格子凸描画できることを示すとともに，そのような描画を求める線形時間アルゴリズムを与える．また，5連結p-k重ドーナツグラフを4連結（3連結）に拡張した，4連結（3連結）p-k重ドーナツグラフGの定義を与える．更に，4連結（3連結）p-k重ドーナツグラフGは，n/(2k-2)+(2k-5) × (2k-1) の面積の整数格子内に格子直線描画できることを示すとともに，そのような描画を求める線形時間アルゴリズムを与える．

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390565162127396736
  • DOI
    10.14923/transinfj.2017pdp0001
  • ISSN
    18810225
    18804535
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ