Pointed drawings of planar graphs.

Area of Science:

• Computational Geometry
• Graph Theory
• Computer Graphics

Background:

• Standard plane straight-line drawings of graphs may not satisfy the condition that every vertex angle is greater than π.
• Achieving specific angle constraints in graph drawings is crucial for various applications.

Purpose of the Study:

• To develop algorithms for constructing crossing-free planar graph drawings where all vertex angles are greater than π.
• To investigate the use of different curve types (biarcs, Bézier curves, circular arcs) for achieving these angle constraints.

Main Methods:

• Algorithms are presented for constructing drawings using tangent-continuous biarcs.
• Algorithms are developed for constructing drawings using quadratic Bézier curves (parabolic arcs).
• The methods accommodate predefined vertex positions from existing straight-line drawings.

Main Results:

• Demonstrated that crossing-free planar graphs can be drawn with vertex angles greater than π using biarcs or parabolic arcs, even with fixed vertex positions.
• Showcased that arbitrary vertex placement allows for drawings with circular arcs while maintaining the angle property.

Conclusions:

• The study provides effective algorithms for generating angle-constrained planar graph drawings.
• The findings expand the possibilities for visually appealing and functionally constrained graph representations in computer graphics and computational geometry.