Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Convex Grid Drawings of Plane Graphs with Pentagonal Contours on O(n2) Grids Lukisan Grid Cembung bagi Graf Satah dengan Kontur Pentagonal dihidupkan O(n2) Grid

Kei SATO, Kazuyuki MIURA

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Dalam lukisan grid cembung graf satah, semua tepi dilukis sebagai segmen garis lurus tanpa sebarang persilangan tepi, semua bucu diletakkan pada titik grid dan semua kitaran muka dilukis sebagai poligon cembung. Graf satah G mempunyai lukisan cembung jika dan hanya jika G disambung tiga secara dalaman, dan graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada (n-1)×(n-1) grid jika sama ada G adalah bersambung tiga atau pokok penguraian komponen bersambung tiga T(G) daripada G mempunyai dua atau tiga daun, di mana n ialah bilangan bucu dalam G. Graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada 2n× 2n grid jika T(G) mempunyai tepat empat daun. Tambahan pula, graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada 6n×n2 grid jika T(G) mempunyai tepat lima daun. Dalam makalah ini, kami menunjukkan bahawa graf satah tiga sambungan dalaman G mempunyai lukisan grid cembung pada 20n× 16n grid jika T(G) mempunyai tepat lima daun. Kami juga membentangkan algoritma untuk mencari lukisan sedemikian dalam masa linear. Ini ialah algoritma pertama yang menemui lukisan grid cembung bagi graf satah sedemikian G dalam grid O(n2) saiz.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1142-1149
Tarikh penerbitan
2021/09/01
Diumumkan
2021/03/10
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.2020DMP0011
Jenis Manuskrip
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
kategori
Graf dan Rangkaian

Pengarang

Kei SATO
  Fukushima University
Kazuyuki MIURA
  Fukushima University

Kata kunci

Contents [show]