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
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.
Akane SETO
Kyoto University
Aleksandar SHURBEVSKI
Kyoto University
Hiroshi NAGAMOCHI
Kyoto University
Peter EADES
University of Sydney
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Akane SETO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, Peter EADES, "Acute Constraints in Straight-Line Drawings of Planar Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 994-1001, September 2019, doi: 10.1587/transfun.E102.A.994.
Abstract: Recent research on graph drawing focuses on Right-Angle-Crossing (RAC) drawings of 1-plane graphs, where each edge is drawn as a straight line and two crossing edges only intersect at right angles. We give a transformation from a restricted case of the RAC drawing problem to a problem of finding a straight-line drawing of a maximal plane graph where some angles are required to be acute. For a restricted version of the latter problem, we show necessary and sufficient conditions for such a drawing to exist, and design an O(n2)-time algorithm that given an n-vertex plane graph produces a desired drawing of the graph or reports that none exists.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.994/_p
Copier
@ARTICLE{e102-a_9_994,
author={Akane SETO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, Peter EADES, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Acute Constraints in Straight-Line Drawings of Planar Graphs},
year={2019},
volume={E102-A},
number={9},
pages={994-1001},
abstract={Recent research on graph drawing focuses on Right-Angle-Crossing (RAC) drawings of 1-plane graphs, where each edge is drawn as a straight line and two crossing edges only intersect at right angles. We give a transformation from a restricted case of the RAC drawing problem to a problem of finding a straight-line drawing of a maximal plane graph where some angles are required to be acute. For a restricted version of the latter problem, we show necessary and sufficient conditions for such a drawing to exist, and design an O(n2)-time algorithm that given an n-vertex plane graph produces a desired drawing of the graph or reports that none exists.},
keywords={},
doi={10.1587/transfun.E102.A.994},
ISSN={1745-1337},
month={September},}
Copier
TY - JOUR
TI - Acute Constraints in Straight-Line Drawings of Planar Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 994
EP - 1001
AU - Akane SETO
AU - Aleksandar SHURBEVSKI
AU - Hiroshi NAGAMOCHI
AU - Peter EADES
PY - 2019
DO - 10.1587/transfun.E102.A.994
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - Recent research on graph drawing focuses on Right-Angle-Crossing (RAC) drawings of 1-plane graphs, where each edge is drawn as a straight line and two crossing edges only intersect at right angles. We give a transformation from a restricted case of the RAC drawing problem to a problem of finding a straight-line drawing of a maximal plane graph where some angles are required to be acute. For a restricted version of the latter problem, we show necessary and sufficient conditions for such a drawing to exist, and design an O(n2)-time algorithm that given an n-vertex plane graph produces a desired drawing of the graph or reports that none exists.
ER -