Oswin Aichholzer, Günter Rote, André Schulz, and Birgit Vogtenhuber:

Pointed drawings of planar graphs

  1. In: Proceedings of the 19th Canadian Conference on Computational Geometry, Ottawa, August 20–22, 2007, Editor: Prosenjit Bose, pp. 237–240.
  2. Computational Geometry, Theory and Applications 45 (2012), 482–494 (special issue for the 19th Canadian Conference on Computational Geometry). doi:10.1016/j.comgeo.2010.08.001 (open access)


We study the problem how to draw a planar graph such that every vertex is incident to an angle greater than 180 degrees. In general a straight-line embedding can not guarantee this property. We present algorithms which construct such drawings with either tangent-continuous biarcs or quadratic Bézier curves (parabolic arcs), even if the positions of the vertices are predefined by a given plane straight-line embedding of the graph. Moreover, the graph can be embedded with circular arcs if the vertices can be placed arbitrarily.

  pdf file
other papers about this subject
Last update: March 4, 2008.