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

Acute Constraints in Straight-Line Drawings of Planar Graphs Contraintes aiguës dans les dessins en ligne droite de graphiques planaires

Akane SETO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, Peter EADES

  • Vues en texte intégral

    0

  • Citer

Résumé:

Des recherches récentes sur le dessin de graphiques se concentrent sur les dessins à angle droit (RAC) de graphiques à 1 plan, où chaque arête est dessinée comme une ligne droite et deux arêtes croisées ne se coupent qu'à angle droit. Nous donnons une transformation d'un cas restreint du problème de dessin RAC à un problème de recherche d'un dessin en ligne droite d'un graphe plan maximal où certains angles doivent être aigus. Pour une version restreinte de ce dernier problème, nous montrons les conditions nécessaires et suffisantes pour qu'un tel dessin existe, et concevons un O(n2)-algorithme de temps qui a donné un n-le graphique plan des sommets produit le dessin souhaité du graphique ou signale qu'il n'en existe pas.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.994-1001
Date de publication
2019/09/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E102.A.994
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Algorithmes graphiques

Auteurs

Akane SETO
  Kyoto University
Aleksandar SHURBEVSKI
  Kyoto University
Hiroshi NAGAMOCHI
  Kyoto University
Peter EADES
  University of Sydney

Mots-clés

Table des matières