La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Grid Drawings of Five-Connected Plane Graphs Dessins de grille de graphiques plans à cinq connexions

Kazuyuki MIURA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Un dessin en grille d'un graphique plan G est un dessin de G sur le plan de sorte que tous les sommets de G sont placés sur des points de grille plane et toutes les arêtes sont dessinées sous forme de segments de ligne droite entre leurs extrémités sans aucune intersection d'arête. Dans cet article, nous donnons un algorithme en temps linéaire pour trouver un dessin de grille d'un graphe plan à 5 connexions donné. G avec cinq sommets ou plus sur la face extérieure. La taille du dessin satisfait W + Hn - 2, où n est le nombre de sommets dans G, W est la largeur et H est la hauteur du dessin de la grille.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1228-1234
Date de publication
2022/09/01
Publicisé
2022/02/16
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2021DMP0010
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Graphiques et réseaux, algorithmes et structures de données

Auteurs

Kazuyuki MIURA
  Fukushima University

Mots-clés

Table des matières