
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Acute Constraints in StraightLine Drawings of Planar Graphs
Akane SETO Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI Peter EADES
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.9
pp.9941001 Publication Date: 2019/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E102.A.994
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Graph algorithms Keyword: graph drawing, 1planarity, right angle crossing, forbidden graph configurations,
Full Text: PDF(1.2MB)>>
Summary:
Recent research on graph drawing focuses on RightAngleCrossing (RAC) drawings of 1plane 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 straightline 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(n^{2})time algorithm that given an nvertex plane graph produces a desired drawing of the graph or reports that none exists.

