throughout this paper , let g=(v , e ) be a simple planar graph without loops , with finite vertex set v and thus a finite set of edges e. we use the natural understanding of a drawing of a graph . vertices are represented as points in the plane and edges as continuous and ( at least piecewise ) differentiable curves connecting the points of adjacent vertices . a drawing is called non - crossing or plane , if the drawn edges do not intersect in their interior . if we consider only topological properties , that is , the order of the edges and consequently of the faces , we refer to this as combinatorial embedding . given a ( combinatorial ) embedding of a graph g , the faces of g are defined as usual . by an ( abstract ) plane graph , we mean an equivalence class of plane drawings under homotopic deformations of the plane . for connected graphs , this amounts to a combinatorial embedding together with a designation of the outer face . for a drawing f(g ) of g we denote the placement of a vertex vv by f(v ) , and the drawing of an edge ee by f(e ) . note that we consider embedded edges to be open , i.e. , the do not contain their endpoints . for simplicity , and as there is no risk of confusion , in the figures we will denote embedded vertices just by v instead of f(v ) . the tangent of an edge f(e ) at a vertex f(v ) is the limit of the tangents to f(e ) when approaching f(v ) along f(e ) . the tangent ray of f(e ) at f(v ) is the open ray along the tangent to f(e ) at f(v ) from f(v ) towards f(e ) . the angle between two consecutive edges incident to a vertex f(v ) is defined as the angle between the corresponding tangent rays at f(v ) that does not contain the tangent ray of any other incident edge . we say that this angle is incident to f(v ) ( and vice versa ) . in the case of a degree two vertex if a vertex has degree at most one , we say that it is incident to one angle ( having value 2 ) . definition 1pointednessa vertex in a drawing f(g ) is called pointed if it is incident to an angle greater than  ( see fig . we say that a vertex is pointed to a face if its large angle lies in this face . a vertex in a drawing f(g ) is called pointed if it is incident to an angle greater than  ( see fig . we say that a vertex is pointed to a face if its large angle lies in this face . if all vertices in a drawing are pointed we call the drawing pointed . for the special case of straight - line drawings , this definition is identical to the classic definition of pointedness , a term which stems from the field of pseudotriangulations . a pseudotriangle is a simple polygon with exactly three vertices with interior angle smaller than . a pseudotriangulation is a plane straight - line graph where every interior face is a pseudotriangle and the outer face is convex . pseudotriangulations have rich applications and are an important geometric data structure , see for example , and the survey . the graphs which can be drawn as pseudotriangulations are well - characterized : a graph is called generically rigid , if its straight - line realization on a generic point set induces a rigid framework ( edges represent fixed length rods and vertices represent joints ) . in two dimensions , there exists an easy combinatorial characterization of generically rigid graphs that become non - rigid after removing an arbitrary edge . , every plane laman graph can be realized as a pointed pseudotriangulation . as a consequence , subsets of plane laman graphs are exactly the graphs that admit a pointed non - crossing straight - line drawing . an operation that preserves the laman property is the so - called henneberg operation of type 1 : adding a new vertex of degree 2 to an existing laman graph will create another laman graph . a simple example of a planar graph that has no pointed straight - line drawing without crossings is the complete graph with four vertices . we consider various incarnations of the problem how to draw a plane graph pointed , using different kinds of edge shapes . with arbitrary smooth curves or polygonal chains , the task of constructing a pointed drawing of a given plane graph is trivial . as natural , but still quite simple edge shapes , we study circular arcs , tangent continuous biarcs , and quadratic bzier curves . a tangent continuous biarc consists of two circular arcs that are joined in a way that they form a c1 continuous curve . a quadratic bzier curve b spanned by three points p1 , pm and p2 is defined by the equationb(t)=(1t)2p1 + 2t(1t)pm+t2p2,t. it lies completely inside the triangle p1pmp2 ( which is also called control polygon of b ) , has p1 and p2 as endpoints , and is tangent to p1pm at p1 and to p2pm at p2 . the class of quadratic bzier curves is the same as the class of parabolic arcs . for example , can we guarantee a free angular space around each vertex bigger than a given fixed angle larger than  ? a vertex in the drawing f(g ) is called -pointed if it is incident to an angle greater than 2. we call a drawing -pointed if every vertex is -pointed . a vertex in the drawing f(g ) is called -pointed if it is incident to an angle greater than 2. we call a drawing -pointed if every vertex is -pointed . in other words , all edges incident to an -pointed vertex emanate in a sector of angle . further , we propose a stronger version of the pointed drawing problem : given a plane straight - line drawing fs(g ) , can we redraw it as a plane pointed drawing with a certain family of edge shapes without moving the vertices ? we call a drawing with this property a pointed redrawing . the motivation of a pointed redrawing is clear : we can benefit from the given drawing and keep its advantages ( e.g. , all vertices are placed on an integer grid or fulfill other optimality criteria ) . a more general redrawing problem would start from a plane embedding with not necessarily straight edges . we consider the problem of pointed redrawings . we show that every plane straight - line drawing fs(g ) can be redrawn pointed and plane with bzier curves as well as with tangent continuous biarcs . we prove that every plane graph can be drawn -pointed with bzier curves , for arbitrary small >0 . we show that by using biarcs as edges , every plane graph can be drawn such that for all vertices v , all incident edges share a common tangent ray at v. this is maybe one of the most beautiful results in this paper from an aesthetic point of view . we further prove that every plane graph can be drawn pointed and plane with circular arcs as edges . for pointed drawings with biarcs , bzier curves , or polygonal chains of length two , we give a tight bound on the number of edges that have to be drawn as non - straight curves ( theorem 3.6 ) . all obtained drawings can be constructed algorithmically , with the exception of the method described in the proof of theorem 3.2 , which needs a disk packing of the plane graph in a preprocessing step . traditionally , graph drawing is mainly concerned with using the simplest class of curves for the edges : straight - line segments . according to frys theorem , every ( simple ) plane graph has a plane straight - line drawing in the euclidean plane . there is a vast literature dealing with the question of efficiently finding plane straight - line drawings that fulfill certain ( optimality ) criteria ( see   for an overview ) . improving work of de fraysseix , pach and pollack , schnyder   proved that every plane graph with n vertices has a plane straight - line drawing where the vertices lie on a grid of size ( n2)(n2 ) . the famous koebe  andreev  thurston circle packing theorem   states that every plane graph can be embedded with straight - line edges in a way such that its vertices correspond to interior disjoint disks , which touch if and only if the corresponding vertices are connected with an edge , see also . we will use both the procedure of de fraysseix , pach and pollack   and circle packings as building blocks in our algorithm . if we relax the condition that the given plane graph has to be simple , frys theorem does not hold , for the simple reason that straight - line drawings are not well defined for loops , and multiple edges between two vertices are excluded . however , with more complex edge shapes , one can ask for crossing - free drawing of planar multigraphs with loops . the most natural approach is to allow circular arcs . drawing multiple edges as circular arcs is no problem , as an edge in a straight - line drawing can be perturbed to any number of close - by circular arcs . the only circular arc between a vertex and itself is a full circle through this vertex . thus , the vertex has to be incident to an angle of at least  , which then is sufficient for any number of nested loops at this vertex . this means that the simple graph containing only the non - loop edges must be drawn as a pointed graph . in section 3.2 , we show that such a drawing exists ( theorem 3.5 ) and as a consequence , we obtain a plane drawing with circular arcs for every planar multigraph ( corollary 3.1 ) . moreover , an o(n)o(n2 ) grid is sufficient to embed the vertices of these drawings . if the edges incident to a vertex point in all directions , it might be hard to place a label close to its vertex . one of the results which we announced in the proceedings version can not be maintained in full generality , see theorem 3.6 below . in section 2 , we consider the problem of pointed redrawings . we show that every plane straight - line drawing fs(g ) can be redrawn pointed and plane with bzier curves as well as with tangent continuous biarcs . we prove that every plane graph can be drawn -pointed with bzier curves , for arbitrary small >0 . we show that by using biarcs as edges , every plane graph can be drawn such that for all vertices v , all incident edges share a common tangent ray at v. this is maybe one of the most beautiful results in this paper from an aesthetic point of view . we further prove that every plane graph can be drawn pointed and plane with circular arcs as edges . for pointed drawings with biarcs , bzier curves , or polygonal chains of length two , we give a tight bound on the number of edges that have to be drawn as non - straight curves ( theorem 3.6 ) . all obtained drawings can be constructed algorithmically , with the exception of the method described in the proof of theorem 3.2 , which needs a disk packing of the plane graph in a preprocessing step . traditionally , graph drawing is mainly concerned with using the simplest class of curves for the edges : straight - line segments . according to frys theorem , every ( simple ) plane graph has a plane straight - line drawing in the euclidean plane . there is a vast literature dealing with the question of efficiently finding plane straight - line drawings that fulfill certain ( optimality ) criteria ( see   for an overview ) . improving work of de fraysseix , pach and pollack , schnyder   proved that every plane graph with n vertices has a plane straight - line drawing where the vertices lie on a grid of size ( n2)(n2 ) . the famous koebe  andreev  thurston circle packing theorem   states that every plane graph can be embedded with straight - line edges in a way such that its vertices correspond to interior disjoint disks , which touch if and only if the corresponding vertices are connected with an edge , see also . we will use both the procedure of de fraysseix , pach and pollack   and circle packings as building blocks in our algorithm . if we relax the condition that the given plane graph has to be simple , frys theorem does not hold , for the simple reason that straight - line drawings are not well defined for loops , and multiple edges between two vertices are excluded . however , with more complex edge shapes , one can ask for crossing - free drawing of planar multigraphs with loops . the most natural approach is to allow circular arcs . drawing multiple edges as circular arcs is no problem , as an edge in a straight - line drawing can be perturbed to any number of close - by circular arcs . the only circular arc between a vertex and itself is a full circle through this vertex . thus , the vertex has to be incident to an angle of at least  , which then is sufficient for any number of nested loops at this vertex . this means that the simple graph containing only the non - loop edges must be drawn as a pointed graph . in section 3.2 , we show that such a drawing exists ( theorem 3.5 ) and as a consequence , we obtain a plane drawing with circular arcs for every planar multigraph ( corollary 3.1 ) . moreover , an o(n)o(n2 ) grid is sufficient to embed the vertices of these drawings . another potential application for constructing pointed drawings of graphs comes from drawing vertex labels . if the edges incident to a vertex point in all directions , it might be hard to place a label close to its vertex . one of the results which we announced in the proceedings version can not be maintained in full generality , see theorem 3.6 below . theorem 2.1for every plane straight - line drawing 
 fs(g ) 
 of a simple planar graph g there exists a pointed plane redrawing 
 fq(g ) 
 with quadratic bzier curves as edges : fq(v)=fs(v ) 
 for all 
 vv , and for every vertex 
 vv , the cyclic order of the edges incident to v in 
 fs(g ) 
 is the same as in 
 fq(g ) . for every plane straight - line drawing 
 fs(g ) 
 of a simple planar graph g there exists a pointed plane redrawing 
 fq(g ) 
 with quadratic bzier curves as edges : fq(v)=fs(v ) 
 for all 
 vv , and for every vertex 
 vv , the cyclic order of the edges incident to v in 
 fs(g ) 
 is the same as in 
 fq(g ) . proofwithout loss of generality assume that in fs(g ) no two vertices have identical x - coordinates or y - coordinates . assume further , that the vertices are sorted by y - coordinates in increasing order.we construct fq(g ) by iteratively replacing the straight - line edges of fs(g ) with quadratic bzier curves . we first replace the edges incident to the bottom - most vertex v1 , then the edges incident to v2 , and so on . during the construction we maintain the following two invariants:(1)for every vertex vi , the tangent rays of all already redrawn edges lie in the open halfplane hi below the horizontal line through fq(vi).(2)the intermediate drawing is plane.when replacing the edges incident to a vertex vi , all edges incident to a vertex vj , with j < i , have already been redrawn by our algorithm ( as all vertices below vi have already been processed ) . let ei = e1,  ,ek be the edges which have not been replaced yet , sorted by absolute slope , such that e1 has the smallest absolute slope . we redraw these edges in increasing order.let e = vivj , j > i be the current edge we want to process ( see fig . 2 ) . due to invariant ( 1 ) and the processing order of the edges incident to vi we can choose a point pm in hi such that the triangle t = fq(vi)pmfq(vj ) does not contain any vertex or part of an edge of the current drawing in its interior . by convention we place pm to the right of fq(vi ) if e has positive slope , otherwise to the left . we use the triangle t as a control polygon for a quadratic bzier curve b with endpoints fq(vi ) and fq(vj ) , which we take as replacement for the straight - line edge fs(e ) . note that b is tangent to fq(vi)pm at fq(vi ) , and thus invariant ( 1 ) still holds for vi . as b lies completely inside t , and t\{fq(vj ) } lies completely inside hj , invariant ( 1 ) for vj and invariant ( 2 ) remain fulfilled as well.having redrawn all edges in this way , we obtain a drawing whose pointedness follows directly from invariant ( 1 ) , and that is plane follows from invariant ( 2).the easiest way to establish that the cyclic order of edges is unchanged is to augment the drawing fs(g ) to a triangulation by adding edges and deleting the corresponding arcs in the final drawing . for a triangulation a with fixed outer face the order of the edges around a vertex is unique up to a global reflection . without loss of generality assume that in fs(g ) no two vertices have identical x - coordinates or y - coordinates . assume further , that the vertices are sorted by y - coordinates in increasing order . we construct fq(g ) by iteratively replacing the straight - line edges of fs(g ) with quadratic bzier curves . we first replace the edges incident to the bottom - most vertex v1 , then the edges incident to v2 , and so on . during the construction we maintain the following two invariants:(1)for every vertex vi , the tangent rays of all already redrawn edges lie in the open halfplane hi below the horizontal line through fq(vi).(2)the intermediate drawing is plane . for every vertex vi , the tangent rays of all already redrawn edges lie in the open halfplane hi below the horizontal line through fq(vi ) . when replacing the edges incident to a vertex vi , all edges incident to a vertex vj , with j < i , have already been redrawn by our algorithm ( as all vertices below vi have already been processed ) . let ei = e1,  ,ek be the edges which have not been replaced yet , sorted by absolute slope , such that e1 has the smallest absolute slope . let e = vivj , j > i be the current edge we want to process ( see fig . 2 ) . due to invariant ( 1 ) and the processing order of the edges incident to vi we can choose a point pm in hi such that the triangle t = fq(vi)pmfq(vj ) does not contain any vertex or part of an edge of the current drawing in its interior . by convention we place pm to the right of fq(vi ) if e has positive slope , otherwise to the left . we use the triangle t as a control polygon for a quadratic bzier curve b with endpoints fq(vi ) and fq(vj ) , which we take as replacement for the straight - line edge fs(e ) . note that b is tangent to fq(vi)pm at fq(vi ) , and thus invariant ( 1 ) still holds for vi . as b lies completely inside t , and t\{fq(vj ) } lies completely inside hj , invariant ( 1 ) for vj and invariant ( 2 ) remain fulfilled as well . having redrawn all edges in this way , we obtain a drawing whose pointedness follows directly from invariant ( 1 ) , and that is plane follows from invariant ( 2 ) . the easiest way to establish that the cyclic order of edges is unchanged is to augment the drawing fs(g ) to a triangulation by adding edges and deleting the corresponding arcs in the final drawing . for a triangulation a with fixed outer face the order of the edges around a vertex is unique up to a global reflection . the technique used in the proof of theorem 2.1 can be modified to show a similar statement for ( tangent continuous ) biarcs due to the following observation . lemma 2.1consider a triangle spanned by three points 
 p1 , 
 pm 
 and 
 p2 . there exists a tangent continuous biarc connecting 
 p1 
 with 
 p2 
 that lies inside the triangle . furthermore , the biarc is tangent to 
 p1pm 
 at one end and tangent to 
 p2pm 
 at the other end . consider a triangle spanned by three points 
 p1 , 
 pm 
 and 
 p2 . there exists a tangent continuous biarc connecting 
 p1 
 with 
 p2 
 that lies inside the triangle . furthermore , the biarc is tangent to 
 p1pm 
 at one end and tangent to 
 p2pm 
 at the other end . the first arc starts in p1 with tangent direction p1pm and touches the line p2pm in some point p. this point on the segment p2pm has the property that the length of pmp is equal to the length of p1pm ( see fig . the center of the arc is found by intersecting the line l1 perpendicular to p1pm through p1 with the line l2 perpendicular to p2pm through p. the second part of the biarc is given by the straight line segment pp2 ( a degenerate circular arc ) . the first arc starts in p1 with tangent direction p1pm and touches the line p2pm in some point p. this point on the segment p2pm has the property that the length of pmp is equal to the length of p1pm ( see fig . the center of the arc is found by intersecting the line l1 perpendicular to p1pm through p1 with the line l2 perpendicular to p2pm through p. the second part of the biarc is given by the straight line segment pp2 ( a degenerate circular arc ) . theorem 2.2for every plane straight - line drawing 
 fs(g ) 
 of a plane graph g there exists a pointed plane redrawing 
 fb(g ) 
 with tangent continuous biarcs as edges : fb(v)=fs(v ) 
 for all 
 vv , and for every vertex 
 vv , the cyclic order of the edges incident to v in 
 fs(g ) 
 is the same as in 
 fb(g ) . for every plane straight - line drawing 
 fs(g ) 
 of a plane graph g there exists a pointed plane redrawing 
 fb(g ) 
 with tangent continuous biarcs as edges : fb(v)=fs(v ) 
 for all 
 vv , and for every vertex 
 vv , the cyclic order of the edges incident to v in 
 fs(g ) 
 is the same as in 
 fb(g ) . whenever we have chosen an appropriate empty triangle for an edge replacement , we place a tangent continuous biarc in it ( as described in lemma 2.1 ) . whenever we have chosen an appropriate empty triangle for an edge replacement , we place a tangent continuous biarc in it ( as described in lemma 2.1 ) . theorem 2.3there is a planar graph 
 g=(v , e ) 
 with a plane straight - line drawing 
 fs(g ) , for which there are no pointed plane drawings 
 fc(g ) 
 with circular arcs as edges such that 
 fc(v)=fs(v ) 
 for all 
 vv . there is a planar graph 
 g=(v , e ) 
 with a plane straight - line drawing 
 fs(g ) , for which there are no pointed plane drawings 
 fc(g ) 
 with circular arcs as edges such that 
 fc(v)=fs(v ) 
 for all 
 vv . vertex vc is placed at the origin , vertex vt at ( 0,2 ) , vertex vl at ( 0.2,1 ) , and vertex vr at ( 0.2,1 ) . the positions of the remaining vertices are obtained by rotating these vertices by 120 degrees . since g is 3-connected and planar , its combinatorial embedding is fixed for any non - crossing drawing . this implies that in any such drawing the edge between vc and vt has to pass through the narrow passage between vl and vr . since we are restricted to circular arcs , the arc connecting vt and vc has to lie in the shaded region depicted in fig . this region is the intersection of the disk touching vt , vl , vc with the disk touching vt , vr , vc . thus , the tangents of two arcs from vc to the convex hull are separated by an angle of at most =165.3 degrees . but in order to make the vertex vc pointed , one of these angles would have to be larger than .   consider the graph g shown in fig . vertex vc is placed at the origin , vertex vt at ( 0,2 ) , vertex vl at ( 0.2,1 ) , and vertex vr at ( 0.2,1 ) . the positions of the remaining vertices are obtained by rotating these vertices by 120 degrees . since g is 3-connected and planar , its combinatorial embedding is fixed for any non - crossing drawing . this implies that in any such drawing the edge between vc and vt has to pass through the narrow passage between vl and vr . since we are restricted to circular arcs , the arc connecting vt and vc has to lie in the shaded region depicted in fig . this region is the intersection of the disk touching vt , vl , vc with the disk touching vt , vr , vc . the region lies inside a wedge of angle =45.3 degrees . thus , the tangents of two arcs from vc to the convex hull are separated by an angle of at most =165.3 degrees . but in order to make the vertex vc pointed , one of these angles would have to be larger than .   larger examples can be constructed easily . as long as a straight - line drawing similar to fig . 4(a ) is contained inside another drawing , a pointed redrawing with circular arcs is impossible . ( instead of just three ) , one can force the largest possible angle free of incident edges at the central vertex to be arbitrary small . in the last section the placement of the points was determined by a given plane straight - line drawing . if the location of the vertices can be chosen arbitrarily , we get the following easy consequence of theorem 2.1 . theorem 3.1for any 
 >0 
 and any plane graph g , there exists a plane drawing 
 fq(g ) 
 with quadratic bzier curves where all vertices are -pointed . for any 
 >0 
 and any plane graph g , there exists a plane drawing 
 fq(g ) 
 with quadratic bzier curves where all vertices are -pointed . proofconsider an arbitrary straight - line drawing fs(g ) . in the proof of theorem 2.1 we showed a construction for a pointed drawing fq(g ) , in which for every vertex v and for every edge e incident to v , the tangent ray of fq(e ) at fq(v ) lies below the horizontal line through fq(v ) . by compressing the x - axis ( i.e. , scaling by a factor less than 1 ) , the large angle at every vertex in the resulting drawing increases towards 2. this modification produces no crossings . moreover , every quadratic bzier curve is transformed to a quadratic bzier curve ( with respect to the compressed control polygon ) . thus , sufficiently compressing fq(g ) results in the desired -pointed drawing fq(g ) . consider an arbitrary straight - line drawing fs(g ) . in the proof of theorem 2.1 we showed a construction for a pointed drawing fq(g ) , in which for every vertex v and for every edge e incident to v , the tangent ray of fq(e ) at fq(v ) lies below the horizontal line through fq(v ) . by compressing the x - axis ( i.e. , scaling by a factor less than 1 ) , the large angle at every vertex in the resulting drawing increases towards 2. this modification produces no crossings . moreover , every quadratic bzier curve is transformed to a quadratic bzier curve ( with respect to the compressed control polygon ) . thus , sufficiently compressing fq(g ) results in the desired -pointed drawing fq(g ) . by similar arguments , it is possible to obtain an -pointed drawing fb(g ) with biarcs . in this case the argumentation is more involved , because compressing a biarc in one direction does not result in another biarc . however , we can modify the proof of theorem 2.1 in the following way : recall that we used as invariant ( 1 ) that for every vertex vi , the tangent rays of all already redrawn edges lie in the open halfplane hi below the horizontal line through fs(vi ) . to obtain a stronger result , we consider vertical double - wedges centered at the embedded vertices with wedge angle  , and redefine the region hi to be the wedge below the horizontal line through the embedded vertex . we compress the x - axis until all edges of the compressed straight - line drawing lie strictly within the double - wedges of their endpoints , and apply the previous approach with the changed invariant to this compressed drawing . a disadvantage of this construction is that the biarcs tend to consist of a circular arc with small radius and a circular arc with infinite radius . for this reason , we present a completely different approach , which also fulfills an even stronger criterion of pointedness . this criterion , namely that all arcs incident to a vertex share a common tangent at this vertex , implies -pointedness for any >0 . theorem 3.2every plane graph 
 g=(v , e ) 
 has a plane pointed drawing 
 fb(g ) 
 with tangent - continuous biarcs as edges such that 
 fb(g ) 
 is pointed . moreover , for every vertex v , all edges incident to v share a common tangent at 
 fb(v ) . the directions of these tangents can be independently specified for each vertex . every plane graph 
 g=(v , e ) 
 has a plane pointed drawing 
 fb(g ) 
 with tangent - continuous biarcs as edges such that 
 fb(g ) 
 is pointed . moreover , for every vertex v , all edges incident to v share a common tangent at 
 fb(v ) . the directions of these tangents can be independently specified for each vertex . we emphasize that the locations of the vertices can not be specified in this theorem . thurston circle packing theorem , every plane graph admits a disk packing , where each disk belongs to a vertex ( which is the center of the disk ) , and two disks touch if and only if the corresponding vertices share an edge.we start with such a disk packing of the graph g ( see   for algorithmic aspects of such packings ) . to get our drawing fb(v ) of the vertices , we place every vertex vi arbitrarily on the boundary of its disk di , avoiding touching points of the disks . the edges incident to thus , we can obtain desired tangent direction for the edges by placing vi on di appropriately . we can avoid the coincidence of vi with a touching point by rotating the whole disk packing . ( there are only finitely many rotations that have to be avoided.)now consider an edge vivje . for the embedded vertex fb(vi ) let ti be the tangent through fb(vi ) to its disk di . furthermore , let pij be the touching point of the two adjacent disks di and dj and let tij be the tangent to di and dj through pij ( see fig . we draw a circular arc ci from fb(vi ) to pij inside di , the center of ci being the crossing of ti and tij . similarly , we draw an arc cj from fb(vj ) to pij inside dj , with center tjtij . we use cicj as drawing for vivj and apply this construction for all edges in e.it is left to show that the constructed drawing is non - crossing . two biarcs could cross only within a disk of the disk packing . consider all circular arcs incident to the embedded vertex fb(vi ) as depicted in fig . all corresponding circles have their centers on ti and are passing through fb(vi ) , which lies on ti as well . thus , any two of these circles intersect only in fb(vi ) , and the constructed drawing is plane.all biarcs incident to an embedded vertex fb(vi ) have a common tangent orthogonal to ti . we can determine this tangent by placing the vertex vi on ci appropriately , avoiding the finitely many touching points of di . thurston circle packing theorem , every plane graph admits a disk packing , where each disk belongs to a vertex ( which is the center of the disk ) , and two disks touch if and only if the corresponding vertices share an edge . we start with such a disk packing of the graph g ( see   for algorithmic aspects of such packings ) . to get our drawing fb(v ) of the vertices , we place every vertex vi arbitrarily on the boundary of its disk di , avoiding touching points of the disks . the edges incident to thus , we can obtain desired tangent direction for the edges by placing vi on di appropriately . we can avoid the coincidence of vi with a touching point by rotating the whole disk packing . for the embedded vertex fb(vi ) let ti be the tangent through fb(vi ) to its disk di . furthermore , let pij be the touching point of the two adjacent disks di and dj and let tij be the tangent to di and dj through pij ( see fig . 5 ) . we draw a circular arc ci from fb(vi ) to pij inside di , the center of ci being the crossing of ti and tij . similarly , we draw an arc cj from fb(vj ) to pij inside dj , with center tjtij . we use cicj as drawing for vivj and apply this construction for all edges in e. it is left to show that the constructed drawing is non - crossing . consider all circular arcs incident to the embedded vertex fb(vi ) as depicted in fig . all corresponding circles have their centers on ti and are passing through fb(vi ) , which lies on ti as well . thus , any two of these circles intersect only in fb(vi ) , and the constructed drawing is plane . all biarcs incident to an embedded vertex fb(vi ) have a common tangent orthogonal to ti . we can determine this tangent by placing the vertex vi on ci appropriately , avoiding the finitely many touching points of di . the above proof leaves some freedom to place the vertices on the boundaries of the corresponding disks . if in the drawing fs(g ) no two disk centers have the same x - coordinate , we can place each vertex on the bottommost point of the boundary of its disk . by this , all biarcs have positive curvature and we have no  s - shaped  biarcs ( see fig . 7 ) . another possibility is to place each vertex viv farthest away from any touching point of its disk di . in this way we can guarantee the radius of any circular arc inside di to be at least ritan2ki , where ri is the radius of di , and ki2 is the degree of vi . unfortunately , in general , we have no control over the radii ri in the disk packing . we assume in this section that no two vertices will get the same y - coordinate in the drawing . definition 3upper horizontally tangent arc , uht - arclet p1 and p2 be two points , where p1 has the larger y - coordinate . we call a circular arc between p1 and p2 
 upper horizontally tangent if it has a horizontal tangent at p1 . 
 definition 4upper horizontally tangent triangle , uht - trianglewe call a drawing of a triangle upper horizontally tangent if all of its edges are drawn as uht - arcs ( see fig . let p1 and p2 be two points , where p1 has the larger y - coordinate . we call a circular arc between p1 and p2 
 upper horizontally tangent if it has a horizontal tangent at p1 . we call a drawing of a triangle upper horizontally tangent if all of its edges are drawn as uht - arcs ( see fig then the angle at 
 p1 
 between 
 h1 
 and  is twice as large as the angle at 
 p1 
 between 
 p1p2 
 and 
 h1 . then the angle at 
 p1 
 between 
 h1 
 and  is twice as large as the angle at 
 p1 
 between 
 p1p2 
 and 
 h1 . this angle is the alternate angle to the angle at p2 between h2 and p2p1 . the triangle p1p2pt is isosceles and hence the angle between p1p2 and p1pt is  as well . thus , the angle between  and p1p2 equals 2.   the situation stated in the lemma is depicted in fig . this angle is the alternate angle to the angle at p2 between h2 and p2p1 . the triangle p1p2pt is isosceles and hence the angle between p1p2 and p1pt is  as well . thus , the angle between  and p1p2 equals 2.   in the following lemma , we restrict the straight - line edges to have an absolute slope less or equal 1 . this implies that the angle between the tangent of an uht - arc at the lower point and the horizontal line through this lower point is at most /2 . as a consequence , the uht - arc is x - monotone and is contained in the axis - parallel bounding rectangle spanned by its endpoints . if(i)the absolute slope of the line segments 
 p1p2 , 
 p2p3 
 and 
 p1p3 
 is smaller than 1 , and(ii)p2 
 lies below the line through 
 p1 
 and 
 p3 , or 
 p2 
 has the highest y - coordinate , 
 then 
 p1 , 
 p2 , and 
 p3 
 span a non - crossing uht - triangle that is oriented in the same way as the straight - line triangle 
 p1p2p3 . that is , the clockwise order of the points around the faces is the same . if(i)the absolute slope of the line segments 
 p1p2 , 
 p2p3 
 and 
 p1p3 
 is smaller than 1 , and(ii)p2 
 lies below the line through 
 p1 
 and 
 p3 , or 
 p2 
 has the highest y - coordinate , 
 then 
 p1 , 
 p2 , and 
 p3 
 span a non - crossing uht - triangle that is oriented in the same way as the straight - line triangle 
 p1p2p3 . that is , the clockwise order of the points around the faces is the same . the absolute slope of the line segments 
 p1p2 , 
 p2p3 
 and 
 p1p3 
 is smaller than 1 , and p2 
 lies below the line through 
 p1 
 and 
 p3 , or 
 p2 
 has the highest y - coordinate , prooflet yi be the y - coordinate of pi , let hi denote the horizontal line passing through pi , and let aij denote the uht - arc between pi and pj.we prove the lemma by case distinction . without loss of generality we assume that y1<y3 . depending on the relative location of y2 we obtain three cases ( see fig . 9).case 1(y2<y1 ) : a13 and a23 can not intersect since they have a common tangent at p3 and do not lie on the same circle . the other pairs of arcs have bounding rectangles with disjoint interior , and hence can not intersect.case 2(y1<y2<y3 ) : again , a13 and a23 do not intersect since they have a common tangent at p3 and do not lie on the same circle . the arcs a12 and a23 have bounding rectangles with disjoint interior , and therefore do not intersect either . since p2 lies below the line segment p1p3 ( condition ( ii ) ) , p2 lies below the arc a13 and p1p3 has larger slope than p1p2 . thus , and due to lemma 3.1 , the angle between the tangent of a13 and h1 is larger than the angle between the tangent of a12 and h1 , meaning that a12 is incident to p1  below  a13 . as the second endpoint of p2 of a12 lies below a13 as well , an intersection of a12 and a13 ( to the right of p1 ) would imply a second such intersection . this is impossible , because the two circles induced by a12 and a13 would intersect three times.case 3(y3<y2 ) : the pairs a23/a12 , and a23/a13 have bounding rectangles with disjoint interior and therefore do not intersect . for the remaining pair of arcs a12 and a13 we apply again lemma 3.1 and observe that a12 is incident to p1  above  a13 . as as well , it follows that an intersection of a12 and a13 ( to the right of p1 ) would again imply that the two circles induced by a12 and a13 intersect three times , which is impossible.since in all three cases , the above - below order of the ( x - monotone ) incident edges at each vertex is preserved , the orientation of the uht - triangle is identical to the orientation of the straight - line triangle . let yi be the y - coordinate of pi , let hi denote the horizontal line passing through pi , and let aij denote the uht - arc between pi and pj . case 1(y2<y1 ) : a13 and a23 can not intersect since they have a common tangent at p3 and do not lie on the same circle . the other pairs of arcs have bounding rectangles with disjoint interior , and hence can not intersect . ( y2<y1 ) : a13 and a23 can not intersect since they have a common tangent at p3 and do not lie on the same circle . the other pairs of arcs have bounding rectangles with disjoint interior , and hence can not intersect . case 2(y1<y2<y3 ) : again , a13 and a23 do not intersect since they have a common tangent at p3 and do not lie on the same circle . the arcs a12 and a23 have bounding rectangles with disjoint interior , and therefore do not intersect either . since p2 lies below the line segment p1p3 ( condition ( ii ) ) , p2 lies below the arc a13 and p1p3 has larger slope than p1p2 . thus , and due to lemma 3.1 , the angle between the tangent of a13 and h1 is larger than the angle between the tangent of a12 and h1 , meaning that a12 is incident to p1  below  a13 . as the second endpoint of p2 of a12 lies below a13 as well , an intersection of a12 and a13 ( to the right of p1 ) would imply a second such intersection . this is impossible , because the two circles induced by a12 and a13 would intersect three times . ( y1<y2<y3 ) : again , a13 and a23 do not intersect since they have a common tangent at p3 and do not lie on the same circle . the arcs a12 and a23 have bounding rectangles with disjoint interior , and therefore do not intersect either . since p2 lies below the line segment p1p3 ( condition ( ii ) ) , p2 lies below the arc a13 and p1p3 has larger slope than p1p2 . thus , and due to lemma 3.1 , the angle between the tangent of a13 and h1 is larger than the angle between the tangent of a12 and h1 , meaning that a12 is incident to p1  below as the second endpoint of p2 of a12 lies below a13 as well , an intersection of a12 and a13 ( to the right of p1 ) would imply a second such intersection . this is impossible , because the two circles induced by a12 and a13 would intersect three times . case 3(y3<y2 ) : the pairs a23/a12 , and a23/a13 have bounding rectangles with disjoint interior and therefore do not intersect . for the remaining pair of arcs a12 and a13 we apply again lemma 3.1 and observe that a12 is incident to p1  above  a13 . as the second endpoint of p2 of a12 lies above a13 as well , it follows that an intersection of a12 and a13 ( to the right of p1 ) would again imply that the two circles induced by a12 and a13 intersect three times , which is impossible . ( y3<y2 ) : the pairs a23/a12 , and a23/a13 have bounding rectangles with disjoint interior and therefore do not intersect . for the remaining pair of arcs a12 and a13 we apply again lemma 3.1 and observe that a12 is incident to p1  above  a13 . as the second endpoint of p2 of a12 lies above a13 as well , it follows that an intersection of a12 and a13 ( to the right of p1 ) would again imply that the two circles induced by a12 and a13 intersect three times , which is impossible . since in all three cases , the above - below order of the ( x - monotone ) incident edges at each vertex is preserved , the orientation of the uht - triangle is identical to the orientation of the straight - line triangle . we continue by constructing a straight - line drawing that allows us to substitute its triangles by uht - triangles . theorem 3.3(see 
 . ) a plane triangulated graph has a plane straight - line drawing on a 
 ( 2n4)(n2 ) 
 grid . a plane triangulated graph has a plane straight - line drawing on a 
 ( 2n4)(n2 ) 
 grid . the vertices are inserted in a special ( so - called canonical ) order , such that the next vertex pk+1 that is inserted can be drawn on the outer face of the graph gk induced by the first k vertices . thereby as invariant it is maintained that the outer boundary of the graph gk ( drawn so far ) forms a chain of pieces of slope 1 , resting on a horizontal basis ( fig . the next vertex pk+1 to be drawn is adjacent to a continuous subsequence of vertices on the outer boundary . to make space for the new edges incident to pk+1 , the boundary of gk is split into three pieces , which are separated from each other by shifting them one unit apart ( fig . the middle piece contains all neighbors of pk+1 except the first and the last one . in   it is shown that one can split the upper boundary of gk at an arbitrary point and shift the pieces apart horizontally , by an arbitrary amount . if an appropriate part of gk inside the shaded area is shifted along , no crossings are created . furthermore , during such a shifting operation , the endpoints of an edge can only be moved farther apart horizontally . theorem 3.4a plane triangulated graph has a plane straight - line drawing on a grid of size 
 ( 4n9)(2n4 ) , with the following additional properties:(a)no edge is vertical.(b)no edge is horizontal.(c)in each triangular face , the vertex with the middle x - coordinate is either the vertex with the highest y - coordinate , or it lies below the opposite edge . proofthe newly created triangles in the incremental construction described above always fulfill property ( c ) , which can be checked directly , and no horizontal edges are created ( property ( b ) ) . the only horizontal edge is the bottom base edge . this horizontal edge can easily be avoided by starting the construction with a non - horizontal base triangle in the first step.to prevent vertical edges , one can split the middle part into two pieces by vertical line through pk+1 and set them apart by two more units ( fig . ( two units are necessary to ensure that the left and right part are separated in total by an even offset ; this guarantees that the position of pk+1 , which is defined by the requirement that its leftmost and rightmost incident edges have slope + 1 and 1 respectively , gets integer coordinates.)adding a vertex preserves the old y - coordinates and the order of the x - coordinates between adjacent vertices , as well as the cyclic order of the edges . as a consequence , properties ( b ) and ( c ) can be guaranteed to hold for previously added vertices after shifting . property ( a ) is preserved because shifting decreases the absolute slope of an already inserted edge , and by the same reasoning , no edge becomes vertical . the initial drawing of the graph g3 with the first three vertices needs a 32 grid . a plane triangulated graph has a plane straight - line drawing on a grid of size 
 ( 4n9)(2n4 ) , with the following additional properties:(a)no edge is vertical.(b)no edge is horizontal.(c)in each triangular face , the vertex with the middle x - coordinate is either the vertex with the highest y - coordinate , or it lies below the opposite edge . no edge is horizontal . in each triangular face , the vertex with the middle x - coordinate is either the vertex with the highest y - coordinate , or it lies below the opposite edge . the newly created triangles in the incremental construction described above always fulfill property ( c ) , which can be checked directly , and no horizontal edges are created ( property ( b ) ) . this horizontal edge can easily be avoided by starting the construction with a non - horizontal base triangle in the first step . to prevent vertical edges , one can split the middle part into two pieces by vertical line through pk+1 and set them apart by two more units ( fig . ( two units are necessary to ensure that the left and right part are separated in total by an even offset ; this guarantees that the position of pk+1 , which is defined by the requirement that its leftmost and rightmost incident edges have slope + 1 and 1 respectively , gets integer coordinates . ) adding a vertex preserves the old y - coordinates and the order of the x - coordinates between adjacent vertices , as well as the cyclic order of the edges . as a consequence , properties ( b ) and ( c ) can be guaranteed to hold for previously added vertices after shifting . property ( a ) is preserved because shifting decreases the absolute slope of an already inserted edge , and by the same reasoning , no edge becomes vertical . the initial drawing of the graph g3 with the first three vertices needs a 32 grid . theorem 3.5every plane graph g has a plane pointed drawing with circular arcs as edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) given an n - vertex plane triangulated graph , the algorithm of theorem 3.4 constructs drawings in which for every edge its absolute slope is less than 2n . by scaling the x - axis by a factor of 2n , we obtain a drawing in which all edges have slopes in the range between 1 and + 1 . in this we substitute every straight - line edge by its corresponding uht - arc . by this substitution , the order of the edges around a vertex is preserved , and every straight - line triangle is replaced by its corresponding uht - triangle . thus , and due to lemma 3.2 , the obtained circular drawing is crossing - free ( edges on the upper hull are non - crossing as they have bounding - rectangles with disjoint interior).around every vertex there is a number of edges that emanate in the horizontal direction , plus a number of additional edges that point upward . thus one can slightly bend every edge upward and achieve a pointed drawing with circular arcs . every plane graph g has a plane pointed drawing with circular arcs as edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) given an n - vertex plane triangulated graph , the algorithm of theorem 3.4 constructs drawings in which for every edge its absolute slope is less than 2n . by scaling the x - axis by a factor of 2n , we obtain a drawing in which all edges have slopes in the range between 1 and + 1 . in this we substitute every straight - line edge by its corresponding uht - arc . by this substitution , the order of the edges around a vertex is preserved , and every straight - line triangle is replaced by its corresponding uht - triangle . thus , and due to lemma 3.2 , the obtained circular drawing is crossing - free ( edges on the upper hull are non - crossing as they have bounding - rectangles with disjoint interior ) . around every vertex there is a number of edges that emanate in the horizontal direction , plus a number of additional edges that point upward . thus one can slightly bend every edge upward and achieve a pointed drawing with circular arcs . due to theorem 3.4 , pointed drawings constructed as above lie on an o(n)o(n2 ) grid . 11 . as a consequence , we obtain the following result about multigraphs with loops , as mentioned in the introduction : corollary 3.1every planar multigraph , possibly with loops , admits a plane drawing with circular arcs , whose vertices lie on an 
 o(n)o(n2 ) 
 grid . every planar multigraph , possibly with loops , admits a plane drawing with circular arcs , whose vertices lie on an 
 o(n)o(n2 ) 
 grid . note that this is no longer true if we insist on a particular combinatorial embedding . for example , we can not have three non - nested loops incident to a vertex . a different way to find a pointed drawing uses the framework established by haas et al . . a combinatorial pseudotriangulation is a planar combinatorial embedding of an ( abstract ) connected planar graph g with an assignment of the tags big / small to the angles of g such that the following conditions are fulfilled:(1)every interior face has exactly three small angles.(2)the outer face has only angles labeled big.(3)every vertex is incident to at most one angle labeled big . if it is incident to a big angle , it is called pointed ( in the face where is has its big angle).(4)a vertex of degree at most 2 is incident to one angle labeled big . an angle assignment that fulfills these conditions . every vertex is incident to at most one angle labeled big . if it is incident to a big angle , it is called pointed ( in the face where is has its big angle ) . a vertex of degree at most 2 is incident to one angle labeled big . by [ 8 , theorem 6 ] , every combinatorial pseudotriangulation whose underlying graph is a laman graph can be embedded as a pseudotriangulation such that every angle with tag big is larger than  in the drawing , and every angle with tag small is smaller than  in the drawing . furthermore , the shape of every face can be specified up to affine transformations [ 8 , theorem 11 ] . lemma 3.3every triangulation with n vertices can be turned into a combinatorial pointed pseudotriangulation by subdividing 
 n3 
 edges , each with exactly one additional vertex . proofwe construct a cpt - assignment by an iterative procedure that is guided by the canonical order of the plane graph ( see theorem 3.3 ) . this can be easily made true for g3 , which is a single triangle . here , the three angles at the boundary get the tag big , and the three interior angles get the tag small . we therefore connect vk+1 with its neighbors on the boundary of gk ( see fig . all new edges that are not on the boundary of gk+1 are subdivided by adding a new vertex on each such edge . the cpt - assignment is extended such that every exterior angle of gk+1 gets the tag big , and all newly added faces have exactly three small angles . every vertex that vanishes from the boundary will now realize its big angle in one of the newly created faces . this operation is a henneberg-1 step and it preserves the laman property of the graph . the vertices that are introduced by subdividing edges are a result of additional henneberg-1 steps . since g3 is a laman graph , also gn = g is a laman graph.in every step we add two edges that are not subdivided , and there are n4 steps necessary to go from g3 to gn . every triangulation with n vertices can be turned into a combinatorial pointed pseudotriangulation by subdividing 
 n3 
 edges , each with exactly one additional vertex . we construct a cpt - assignment by an iterative procedure that is guided by the canonical order of the plane graph ( see theorem 3.3 ) . this can be easily made true for g3 , which is a single triangle . here , the three angles at the boundary get the tag big , and the three interior angles get the tag small . we therefore connect vk+1 with its neighbors on the boundary of gk ( see fig . all new edges that are not on the boundary of gk+1 are subdivided by adding a new vertex on each such edge . the cpt - assignment is extended such that every exterior angle of gk+1 gets the tag big , and all newly added faces have exactly three small angles . every vertex that vanishes from the boundary will now realize its big angle in one of the newly created faces . this operation is a henneberg-1 step and it preserves the laman property of the graph . the vertices that are introduced by subdividing edges are a result of additional henneberg-1 steps . since g3 is a laman graph , also gn = g is a laman graph . in every step we add two edges that are not subdivided , and there are n4 steps necessary to go from g3 to gn . theorem 3.6every plane graph g with n vertices has a plane pointed drawing with either quadratic bzier curves , tangent continuous biarcs , or 2-chains ( polygonal chains consisting of two line segments ) , which uses at most 
 n3 
 non - straight edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) as a first step , we turn g into a combinatorial pointed pseudotriangulation as done in lemma 3.3 . by this we creates four types of bounded faces:(i)triangles,(ii)quadrilaterals with a degree-2 vertex with big angle,(iii)quadrilaterals with a degree-2 vertex with small angle and the big angle is realized next to it,(iv)pentagons with two non - adjacent degree-2 vertices , one of them with a big , one of them with a small angle . we apply the algorithm of   to realize the combinatorial pseudotriangulation . in all faces of type ( iii ) the interior of the triangle spanned by the degree-2 vertex and its two neighbors is empty , see fig . however , the algorithm of   allows us to specify the face shapes up to affine transformations . by giving all faces of type ( iv ) the shape shown in fig . this property is preserved under affine transformations.what we have obtained so far is a pointed drawing , where at most n3 edges are drawn as 2-chains , which proves the theorem for the case of polygonal chains.for the case of bzier curves or biarcs , we consider for each 2-chain p1 , pm , p2 ( with pm being the vertex of degree two ) the triangle =p1pmp2 . lies in a pseudotriangle in which pm has a small angle . due to the affine shape of the faces we use these triangles as control polygons as shown in fig . 13 and replace the 2-chains by bzier curves or biarcs ( similar to lemma 2.1 ) . every plane graph g with n vertices has a plane pointed drawing with either quadratic bzier curves , tangent continuous biarcs , or 2-chains ( polygonal chains consisting of two line segments ) , which uses at most 
 n3 
 non - straight edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) as a first step , we turn g into a combinatorial pointed pseudotriangulation as done in lemma 3.3 . by this we creates four types of bounded faces:(i)triangles,(ii)quadrilaterals with a degree-2 vertex with big angle,(iii)quadrilaterals with a degree-2 vertex with small angle and the big angle is realized next to it,(iv)pentagons with two non - adjacent degree-2 vertices , one of them with a big , one of them with a small angle . we apply the algorithm of   to realize the combinatorial pseudotriangulation . in all faces of type ( iii ) the interior of the triangle spanned by the degree-2 vertex and its two neighbors is empty , see fig . however , the algorithm of   allows us to specify the face shapes up to affine transformations . by giving all faces of type ( iv ) the shape shown in fig . quadrilaterals with a degree-2 vertex with big angle , quadrilaterals with a degree-2 vertex with small angle and the big angle is realized next to it , pentagons with two non - adjacent degree-2 vertices , one of them with a big , one of them with a small angle . what we have obtained so far is a pointed drawing , where at most n3 edges are drawn as 2-chains , which proves the theorem for the case of polygonal chains . for the case of bzier curves or biarcs , we consider for each 2-chain p1 , pm , p2 ( with pm being the vertex of degree two ) the triangle =p1pmp2 . lies in a pseudotriangle in which pm has a small angle . due to the affine shape of the faces we use these triangles as control polygons as shown in fig . 13 and replace the 2-chains by bzier curves or biarcs ( similar to lemma 2.1 ) . in general it is not possible to draw a planar graph pointed using a larger number of ( non - crossing ) straight - line edges , since every maximal pointed straight - line graph has at most 2n3 edges , and due to eulers formula a triangulation has 3n6 edges . in this sense , the big angles of the cpt - assignment and the subdivisions computed by our method are shown in fig . 14(c ) and finally to a pointed drawing with only three bzier curves as shown in fig . 14(d ) . in the proceedings version of this paper , we made a stronger claim [ 1 , theorem 7 ] : for each inner vertex , the face in which it is pointed can be chosen arbitrarily . it is not possible to make the three marked angles big with at most n3 non - straight edges which are either quadratic bzier curves or 2-chains . the reason is that a single quadratic bzier curve bends by less than . therefore , in a triangle with three vertices that are pointed in the interior face , all three edges must be curved , see fig . 15(b ) : if we proceed clockwise along the boundary , the tangent direction turns right by less than  along each edge . at each vertex , it makes a left turn , by pointedness . with less than three curved edges , the tangent direction can not complete a full right turn of 2. the same argument works for 2-chains . by a similar argument , a triangle with two vertices that are pointed in the interior face needs at least two curved edges . applying these facts to our example , we see that all three edges in the triangle abc must be curved . with a total of n=6 vertices , we have thus exhausted our reservoir of at most n3=3 non - straight edges . ac together with the curved edge bc can not make pointed interior angles at b and c in the triangle abc . this example does not rule out the possibility that pointedness in the chosen faces can be achieved with more than n3 curved edges , or with biarcs . in the last section the placement of the points was determined by a given plane straight - line drawing . if the location of the vertices can be chosen arbitrarily , we get the following easy consequence of theorem 2.1 . theorem 3.1for any 
 >0 
 and any plane graph g , there exists a plane drawing 
 fq(g ) 
 with quadratic bzier curves where all vertices are -pointed . for any 
 >0 
 and any plane graph g , there exists a plane drawing 
 fq(g ) 
 with quadratic bzier curves where all vertices are -pointed . proofconsider an arbitrary straight - line drawing fs(g ) . in the proof of theorem 2.1 we showed a construction for a pointed drawing fq(g ) , in which for every vertex v and for every edge e incident to v , the tangent ray of fq(e ) at fq(v ) lies below the horizontal line through fq(v ) . by compressing the x - axis ( i.e. , scaling by a factor less than 1 ) , the large angle at every vertex in the resulting drawing increases towards 2. this modification produces no crossings . moreover , every quadratic bzier curve is transformed to a quadratic bzier curve ( with respect to the compressed control polygon ) . thus , sufficiently compressing fq(g ) results in the desired -pointed drawing fq(g ) . consider an arbitrary straight - line drawing fs(g ) . in the proof of theorem 2.1 we showed a construction for a pointed drawing fq(g ) , in which for every vertex v and for every edge e incident to v , the tangent ray of fq(e ) at fq(v ) lies below the horizontal line through fq(v ) . by compressing the x - axis ( i.e. , scaling by a factor less than 1 ) , the large angle at every vertex in the resulting drawing increases towards 2. this modification produces no crossings . moreover , every quadratic bzier curve is transformed to a quadratic bzier curve ( with respect to the compressed control polygon ) . thus , sufficiently compressing fq(g ) results in the desired -pointed drawing fq(g ) . by similar arguments , it is possible to obtain an -pointed drawing fb(g ) with biarcs . in this case the argumentation is more involved , because compressing a biarc in one direction does not result in another biarc . however , we can modify the proof of theorem 2.1 in the following way : recall that we used as invariant ( 1 ) that for every vertex vi , the tangent rays of all already redrawn edges lie in the open halfplane hi below the horizontal line through fs(vi ) . to obtain a stronger result , we consider vertical double - wedges centered at the embedded vertices with wedge angle  , and redefine the region hi to be the wedge below the horizontal line through the embedded vertex . we compress the x - axis until all edges of the compressed straight - line drawing lie strictly within the double - wedges of their endpoints , and apply the previous approach with the changed invariant to this compressed drawing . a disadvantage of this construction is that the biarcs tend to consist of a circular arc with small radius and a circular arc with infinite radius . for this reason , we present a completely different approach , which also fulfills an even stronger criterion of pointedness . this criterion , namely that all arcs incident to a vertex share a common tangent at this vertex , implies -pointedness for any >0 . theorem 3.2every plane graph 
 g=(v , e ) 
 has a plane pointed drawing 
 fb(g ) 
 with tangent - continuous biarcs as edges such that 
 fb(g ) 
 is pointed . moreover , for every vertex v , all edges incident to v share a common tangent at 
 fb(v ) . the directions of these tangents can be independently specified for each vertex . every plane graph 
 g=(v , e ) 
 has a plane pointed drawing 
 fb(g ) 
 with tangent - continuous biarcs as edges such that 
 fb(g ) 
 is pointed . moreover , for every vertex v , all edges incident to v share a common tangent at 
 fb(v ) . the directions of these tangents can be independently specified for each vertex . we emphasize that the locations of the vertices can not be specified in this theorem . thurston circle packing theorem , every plane graph admits a disk packing , where each disk belongs to a vertex ( which is the center of the disk ) , and two disks touch if and only if the corresponding vertices share an edge.we start with such a disk packing of the graph g ( see   for algorithmic aspects of such packings ) . to get our drawing fb(v ) of the vertices , we place every vertex vi arbitrarily on the boundary of its disk di , avoiding touching points of the disks . the edges incident to thus , we can obtain desired tangent direction for the edges by placing vi on di appropriately . we can avoid the coincidence of vi with a touching point by rotating the whole disk packing . ( there are only finitely many rotations that have to be avoided.)now consider an edge vivje . for the embedded vertex fb(vi ) let ti be the tangent through fb(vi ) to its disk di . furthermore , let pij be the touching point of the two adjacent disks di and dj and let tij be the tangent to di and dj through pij ( see fig . we draw a circular arc ci from fb(vi ) to pij inside di , the center of ci being the crossing of ti and tij . similarly , we draw an arc cj from fb(vj ) to pij inside dj , with center tjtij . we use cicj as drawing for vivj and apply this construction for all edges in e.it is left to show that the constructed drawing is non - crossing . two biarcs could cross only within a disk of the disk packing . consider all circular arcs incident to the embedded vertex fb(vi ) as depicted in fig . all corresponding circles have their centers on ti and are passing through fb(vi ) , which lies on ti as well . thus , any two of these circles intersect only in fb(vi ) , and the constructed drawing is plane.all biarcs incident to an embedded vertex fb(vi ) have a common tangent orthogonal to ti . we can determine this tangent by placing the vertex vi on ci appropriately , avoiding the finitely many touching points of di . thurston circle packing theorem , every plane graph admits a disk packing , where each disk belongs to a vertex ( which is the center of the disk ) , and two disks touch if and only if the corresponding vertices share an edge . we start with such a disk packing of the graph g ( see   for algorithmic aspects of such packings ) . to get our drawing fb(v ) of the vertices , we place every vertex vi arbitrarily on the boundary of its disk di , avoiding touching points of the disks . the edges incident to thus , we can obtain desired tangent direction for the edges by placing vi on di appropriately . we can avoid the coincidence of vi with a touching point by rotating the whole disk packing . for the embedded vertex fb(vi ) let ti be the tangent through fb(vi ) to its disk di . furthermore , let pij be the touching point of the two adjacent disks di and dj and let tij be the tangent to di and dj through pij ( see fig . 5 ) . we draw a circular arc ci from fb(vi ) to pij inside di , the center of ci being the crossing of ti and tij . similarly , we draw an arc cj from fb(vj ) to pij inside dj , with center tjtij . we use cicj as drawing for vivj and apply this construction for all edges in e. it is left to show that the constructed drawing is non - crossing . consider all circular arcs incident to the embedded vertex fb(vi ) as depicted in fig . all corresponding circles have their centers on ti and are passing through fb(vi ) , which lies on ti as well . thus , any two of these circles intersect only in fb(vi ) , and the constructed drawing is plane . all biarcs incident to an embedded vertex fb(vi ) have a common tangent orthogonal to ti . we can determine this tangent by placing the vertex vi on ci appropriately , avoiding the finitely many touching points of di . the above proof leaves some freedom to place the vertices on the boundaries of the corresponding disks . if in the drawing fs(g ) no two disk centers have the same x - coordinate , we can place each vertex on the bottommost point of the boundary of its disk . by this , all biarcs have positive curvature and we have no  s - shaped  biarcs ( see fig . 7 ) . another possibility is to place each vertex viv farthest away from any touching point of its disk di . in this way we can guarantee the radius of any circular arc inside di to be at least ritan2ki , where ri is the radius of di , and ki2 is the degree of vi . unfortunately , in general , we have no control over the radii ri in the disk packing . we assume in this section that no two vertices will get the same y - coordinate in the drawing . definition 3upper horizontally tangent arc , uht - arclet p1 and p2 be two points , where p1 has the larger y - coordinate . we call a circular arc between p1 and p2 
 upper horizontally tangent if it has a horizontal tangent at p1 . 
 definition 4upper horizontally tangent triangle , uht - trianglewe call a drawing of a triangle upper horizontally tangent if all of its edges are drawn as uht - arcs ( see fig . let p1 and p2 be two points , where p1 has the larger y - coordinate . we call a circular arc between p1 and p2 
 upper horizontally tangent if it has a horizontal tangent at p1 . we call a drawing of a triangle upper horizontally tangent if all of its edges are drawn as uht - arcs ( see fig . 9 ) . for any two points , then the angle at 
 p1 
 between 
 h1 
 and  is twice as large as the angle at 
 p1 
 between 
 p1p2 
 and 
 h1 . then the angle at 
 p1 
 between 
 h1 
 and  is twice as large as the angle at 
 p1 
 between 
 p1p2 
 and 
 h1 . this angle is the alternate angle to the angle at p2 between h2 and p2p1 . the triangle p1p2pt is isosceles and hence the angle between p1p2 and p1pt is  as well . thus , the angle between  and p1p2 equals 2.   the situation stated in the lemma is depicted in fig . this angle is the alternate angle to the angle at p2 between h2 and p2p1 . the triangle p1p2pt is isosceles and hence the angle between p1p2 and p1pt is  as well . thus , the angle between  and p1p2 equals 2.   in the following lemma , we restrict the straight - line edges to have an absolute slope less or equal 1 . this implies that the angle between the tangent of an uht - arc at the lower point and the horizontal line through this lower point is at most /2 . as a consequence , the uht - arc is x - monotone and is contained in the axis - parallel bounding rectangle spanned by its endpoints . if(i)the absolute slope of the line segments 
 p1p2 , 
 p2p3 
 and 
 p1p3 
 is smaller than 1 , and(ii)p2 
 lies below the line through 
 p1 
 and 
 p3 , or 
 p2 
 has the highest y - coordinate , 
 then 
 p1 , 
 p2 , and 
 p3 
 span a non - crossing uht - triangle that is oriented in the same way as the straight - line triangle 
 p1p2p3 . that is , the clockwise order of the points around the faces is the same . if(i)the absolute slope of the line segments 
 p1p2 , 
 p2p3 
 and 
 p1p3 
 is smaller than 1 , and(ii)p2 
 lies below the line through 
 p1 
 and 
 p3 , or 
 p2 
 has the highest y - coordinate , 
 then 
 p1 , 
 p2 , and 
 p3 
 span a non - crossing uht - triangle that is oriented in the same way as the straight - line triangle 
 p1p2p3 . that is , the clockwise order of the points around the faces is the same . the absolute slope of the line segments 
 p1p2 , 
 p2p3 
 and 
 p1p3 
 is smaller than 1 , and p2 
 lies below the line through 
 p1 
 and 
 p3 , or 
 p2 
 has the highest y - coordinate , prooflet yi be the y - coordinate of pi , let hi denote the horizontal line passing through pi , and let aij denote the uht - arc between pi and pj.we prove the lemma by case distinction . without loss of generality 9).case 1(y2<y1 ) : a13 and a23 can not intersect since they have a common tangent at p3 and do not lie on the same circle . the other pairs of arcs have bounding rectangles with disjoint interior , and hence can not intersect.case 2(y1<y2<y3 ) : again , a13 and a23 do not intersect since they have a common tangent at p3 and do not lie on the same circle . the arcs a12 and a23 have bounding rectangles with disjoint interior , and therefore do not intersect either . since p2 lies below the line segment p1p3 ( condition ( ii ) ) , p2 lies below the arc a13 and p1p3 has larger slope than p1p2 . thus , and due to lemma 3.1 , the angle between the tangent of a13 and h1 is larger than the angle between the tangent of a12 and h1 , meaning that a12 is incident to p1  below  a13 . as the second endpoint of p2 of a12 lies below a13 as well , an intersection of a12 and a13 ( to the right of p1 ) would imply a second such intersection . this is impossible , because the two circles induced by a12 and a13 would intersect three times.case 3(y3<y2 ) : the pairs a23/a12 , and a23/a13 have bounding rectangles with disjoint interior and therefore do not intersect . for the remaining pair of arcs a12 and a13 we apply again lemma 3.1 and observe that a12 is incident to p1  above  a13 . as as well , it follows that an intersection of a12 and a13 ( to the right of p1 ) would again imply that the two circles induced by a12 and a13 intersect three times , which is impossible.since in all three cases , the above - below order of the ( x - monotone ) incident edges at each vertex is preserved , the orientation of the uht - triangle is identical to the orientation of the straight - line triangle . let yi be the y - coordinate of pi , let hi denote the horizontal line passing through pi , and let aij denote the uht - arc between pi and pj . case 1(y2<y1 ) : a13 and a23 can not intersect since they have a common tangent at p3 and do not lie on the same circle . the other pairs of arcs have bounding rectangles with disjoint interior , and hence can not intersect . ( y2<y1 ) : a13 and a23 can not intersect since they have a common tangent at p3 and do not lie on the same circle . the other pairs of arcs have bounding rectangles with disjoint interior , and hence can not intersect . case 2(y1<y2<y3 ) : again , a13 and a23 do not intersect since they have a common tangent at p3 and do not lie on the same circle . the arcs a12 and a23 have bounding rectangles with disjoint interior , and therefore do not intersect either . since p2 lies below the line segment p1p3 ( condition ( ii ) ) , p2 lies below the arc a13 and p1p3 has larger slope than p1p2 . thus , and due to lemma 3.1 , the angle between the tangent of a13 and h1 is larger than the angle between the tangent of a12 and h1 , meaning that a12 is incident to p1  below  a13 . as the second endpoint of p2 of a12 lies below a13 as well , an intersection of a12 and a13 ( to the right of p1 ) would imply a second such intersection . this is impossible , because the two circles induced by a12 and a13 would intersect three times . ( y1<y2<y3 ) : again , a13 and a23 do not intersect since they have a common tangent at p3 and do not lie on the same circle . the arcs a12 and a23 have bounding rectangles with disjoint interior , and therefore do not intersect either . since p2 lies below the line segment p1p3 ( condition ( ii ) ) , p2 lies below the arc a13 and p1p3 has larger slope than p1p2 . thus , and due to lemma 3.1 , the angle between the tangent of a13 and h1 is larger than the angle between the tangent of a12 and h1 , meaning that a12 is incident to p1  below as the second endpoint of p2 of a12 lies below a13 as well , an intersection of a12 and a13 ( to the right of p1 ) would imply a second such intersection . this is impossible , because the two circles induced by a12 and a13 would intersect three times . case 3(y3<y2 ) : the pairs a23/a12 , and a23/a13 have bounding rectangles with disjoint interior and therefore do not intersect . for the remaining pair of arcs a12 and a13 we apply again lemma 3.1 and observe that a12 is incident to p1  above  a13 . as a13 as well , it follows that an intersection of a12 and a13 ( to the right of p1 ) would again imply that the two circles induced by a12 and a13 intersect three times , which is impossible . ( y3<y2 ) : the pairs a23/a12 , and a23/a13 have bounding rectangles with disjoint interior and therefore do not intersect . for the remaining pair of arcs a12 and a13 we apply again lemma 3.1 and observe that a12 is incident to p1  above  a13 . as as well , it follows that an intersection of a12 and a13 ( to the right of p1 ) would again imply that the two circles induced by a12 and a13 intersect three times , which is impossible . since in all three cases , the above - below order of the ( x - monotone ) incident edges at each vertex is preserved , the orientation of the uht - triangle is identical to the orientation of the straight - line triangle . we continue by constructing a straight - line drawing that allows us to substitute its triangles by uht - triangles . theorem 3.3(see 
 . ) a plane triangulated graph has a plane straight - line drawing on a 
 ( 2n4)(n2 ) 
 grid . a plane triangulated graph has a plane straight - line drawing on a 
 ( 2n4)(n2 ) 
 grid . the vertices are inserted in a special ( so - called canonical ) order , such that the next vertex pk+1 that is inserted can be drawn on the outer face of the graph gk induced by the first k vertices . thereby as invariant it is maintained that the outer boundary of the graph gk ( drawn so far ) forms a chain of pieces of slope 1 , resting on a horizontal basis ( fig . the next vertex pk+1 to be drawn is adjacent to a continuous subsequence of vertices on the outer boundary . to make space for the new edges incident to pk+1 , the boundary of gk is split into three pieces , which are separated from each other by shifting them one unit apart ( fig . 10(b ) ) . the middle piece contains all neighbors of pk+1 except the first and the last one . in   it is shown that one can split the upper boundary of gk at an arbitrary point and shift the pieces apart horizontally , by an arbitrary amount . if an appropriate part of gk inside the shaded area is shifted along , no crossings are created . furthermore , during such a shifting operation , the endpoints of an edge can only be moved farther apart horizontally . theorem 3.4a plane triangulated graph has a plane straight - line drawing on a grid of size 
 ( 4n9)(2n4 ) , with the following additional properties:(a)no edge is vertical.(b)no edge is horizontal.(c)in each triangular face , the vertex with the middle x - coordinate is either the vertex with the highest y - coordinate , or it lies below the opposite edge . proofthe newly created triangles in the incremental construction described above always fulfill property ( c ) , which can be checked directly , and no horizontal edges are created ( property ( b ) ) . the only horizontal edge is the bottom base edge . this horizontal edge can easily be avoided by starting the construction with a non - horizontal base triangle in the first step.to prevent vertical edges , one can split the middle part into two pieces by vertical line through pk+1 and set them apart by two more units ( fig . ( two units are necessary to ensure that the left and right part are separated in total by an even offset ; this guarantees that the position of pk+1 , which is defined by the requirement that its leftmost and rightmost incident edges have slope + 1 and 1 respectively , gets integer coordinates.)adding a vertex preserves the old y - coordinates and the order of the x - coordinates between adjacent vertices , as well as the cyclic order of the edges . as a consequence , properties ( b ) and ( c ) can be guaranteed to hold for previously added vertices after shifting . property ( a ) is preserved because shifting decreases the absolute slope of an already inserted edge , and by the same reasoning , no edge becomes vertical . the initial drawing of the graph g3 with the first three vertices needs a 32 grid . a plane triangulated graph has a plane straight - line drawing on a grid of size 
 ( 4n9)(2n4 ) , with the following additional properties:(a)no edge is vertical.(b)no edge is horizontal.(c)in each triangular face , the vertex with the middle x - coordinate is either the vertex with the highest y - coordinate , or it lies below the opposite edge . no edge is horizontal . in each triangular face , the vertex with the middle x - coordinate is either the vertex with the highest y - coordinate , or it lies below the opposite edge . the newly created triangles in the incremental construction described above always fulfill property ( c ) , which can be checked directly , and no horizontal edges are created ( property ( b ) ) . this horizontal edge can easily be avoided by starting the construction with a non - horizontal base triangle in the first step . to prevent vertical edges , one can split the middle part into two pieces by vertical line through pk+1 and set them apart by two more units ( fig . ( two units are necessary to ensure that the left and right part are separated in total by an even offset ; this guarantees that the position of pk+1 , which is defined by the requirement that its leftmost and rightmost incident edges have slope + 1 and 1 respectively , gets integer coordinates . ) adding a vertex preserves the old y - coordinates and the order of the x - coordinates between adjacent vertices , as well as the cyclic order of the edges . as a consequence , properties ( b ) and ( c ) can be guaranteed to hold for previously added vertices after shifting . property ( a ) is preserved because shifting decreases the absolute slope of an already inserted edge , and by the same reasoning , no edge becomes vertical . the initial drawing of the graph g3 with the first three vertices needs a 32 grid . theorem 3.5every plane graph g has a plane pointed drawing with circular arcs as edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) given an n - vertex plane triangulated graph , the algorithm of theorem 3.4 constructs drawings in which for every edge its absolute slope is less than 2n . by scaling the x - axis by a factor of 2n , we obtain a drawing in which all edges have slopes in the range between 1 and + 1 . in this we substitute every straight - line edge by its corresponding uht - arc . by this substitution , the order of the edges around a vertex is preserved , and every straight - line triangle is replaced by its corresponding uht - triangle . thus , and due to lemma 3.2 , the obtained circular drawing is crossing - free ( edges on the upper hull are non - crossing as they have bounding - rectangles with disjoint interior).around every vertex there is a number of edges that emanate in the horizontal direction , plus a number of additional edges that point upward . thus one can slightly bend every edge upward and achieve a pointed drawing with circular arcs . every plane graph g has a plane pointed drawing with circular arcs as edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) given an n - vertex plane triangulated graph , the algorithm of theorem 3.4 constructs drawings in which for every edge its absolute slope is less than 2n . by scaling the x - axis by a factor of 2n , we obtain a drawing in which all edges have slopes in the range between 1 and + 1 . in this we substitute every straight - line edge by its corresponding uht - arc . by this substitution , the order of the edges around a vertex is preserved , and every straight - line triangle is replaced by its corresponding uht - triangle . thus , and due to lemma 3.2 , the obtained circular drawing is crossing - free ( edges on the upper hull are non - crossing as they have bounding - rectangles with disjoint interior ) . around every vertex there is a number of edges that emanate in the horizontal direction , plus a number of additional edges that point upward . thus one can slightly bend every edge upward and achieve a pointed drawing with circular arcs . due to theorem 3.4 , pointed drawings constructed as above lie on an o(n)o(n2 ) grid . we obtain the following result about multigraphs with loops , as mentioned in the introduction : corollary 3.1every planar multigraph , possibly with loops , admits a plane drawing with circular arcs , whose vertices lie on an 
 o(n)o(n2 ) 
 grid . every planar multigraph , possibly with loops , admits a plane drawing with circular arcs , whose vertices lie on an 
 o(n)o(n2 ) 
 grid . note that this is no longer true if we insist on a particular combinatorial embedding . for example , we can not have three non - nested loops incident to a vertex . a different way to find a pointed drawing uses the framework established by haas et al . . a combinatorial pseudotriangulation is a planar combinatorial embedding of an ( abstract ) connected planar graph g with an assignment of the tags big / small to the angles of g such that the following conditions are fulfilled:(1)every interior face has exactly three small angles.(2)the outer face has only angles labeled big.(3)every vertex is incident to at most one angle labeled big . if it is incident to a big angle , it is called pointed ( in the face where is has its big angle).(4)a vertex of degree at most 2 is incident to one angle labeled big . an angle assignment that fulfills these conditions every vertex is incident to at most one angle labeled big . if it is incident to a big angle , it is called pointed ( in the face where is has its big angle ) . a vertex of degree at most 2 is incident to one angle labeled big . by [ 8 , theorem 6 ] , every combinatorial pseudotriangulation whose underlying graph is a laman graph can be embedded as a pseudotriangulation such that every angle with tag big is larger than  in the drawing , and every angle with tag small is smaller than  in the drawing . furthermore , the shape of every face can be specified up to affine transformations [ 8 , theorem 11 ] . lemma 3.3every triangulation with n vertices can be turned into a combinatorial pointed pseudotriangulation by subdividing 
 n3 
 edges , each with exactly one additional vertex . proofwe construct a cpt - assignment by an iterative procedure that is guided by the canonical order of the plane graph ( see theorem 3.3 ) . this can be easily made true for g3 , which is a single triangle . here , the three angles at the boundary get the tag big , and the three interior angles get the tag small . we therefore connect vk+1 with its neighbors on the boundary of gk ( see fig . all new edges that are not on the boundary of gk+1 are subdivided by adding a new vertex on each such edge . the cpt - assignment is extended such that every exterior angle of gk+1 gets the tag big , and all newly added faces have exactly three small angles . every vertex that vanishes from the boundary will now realize its big angle in one of the newly created faces . this operation is a henneberg-1 step and it preserves the laman property of the graph . the vertices that are introduced by subdividing edges are a result of additional henneberg-1 steps . since g3 is a laman graph , also gn = g is a laman graph.in every step we add two edges that are not subdivided , and there are n4 steps necessary to go from g3 to gn . every triangulation with n vertices can be turned into a combinatorial pointed pseudotriangulation by subdividing 
 n3 
 edges , each with exactly one additional vertex . we construct a cpt - assignment by an iterative procedure that is guided by the canonical order of the plane graph ( see theorem 3.3 ) . this can be easily made true for g3 , which is a single triangle . here , the three angles at the boundary get the tag big , and the three interior angles get the tag small . we therefore connect vk+1 with its neighbors on the boundary of gk ( see fig . all new edges that are not on the boundary of gk+1 are subdivided by adding a new vertex on each such edge . the cpt - assignment is extended such that every exterior angle of gk+1 gets the tag big , and all newly added faces have exactly three small angles . every vertex that vanishes from the boundary will now realize its big angle in one of the newly created faces . this operation is a henneberg-1 step and it preserves the laman property of the graph . the vertices that are introduced by subdividing edges are a result of additional henneberg-1 steps . since g3 is a laman graph , also gn = g is a laman graph . in every step we add two edges that are not subdivided , and there are n4 steps necessary to go from g3 to gn . theorem 3.6every plane graph g with n vertices has a plane pointed drawing with either quadratic bzier curves , tangent continuous biarcs , or 2-chains ( polygonal chains consisting of two line segments ) , which uses at most 
 n3 
 non - straight edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) as a first step , we turn g into a combinatorial pointed pseudotriangulation as done in lemma 3.3 . by this we creates four types of bounded faces:(i)triangles,(ii)quadrilaterals with a degree-2 vertex with big angle,(iii)quadrilaterals with a degree-2 vertex with small angle and the big angle is realized next to it,(iv)pentagons with two non - adjacent degree-2 vertices , one of them with a big , one of them with a small angle . we apply the algorithm of   to realize the combinatorial pseudotriangulation . in all faces of type ( iii ) the interior of the triangle spanned by the degree-2 vertex and its two neighbors is empty , see fig . however , the algorithm of   allows us to specify the face shapes up to affine transformations . by giving all faces of type ( iv ) the shape shown in fig . this property is preserved under affine transformations.what we have obtained so far is a pointed drawing , where at most n3 edges are drawn as 2-chains , which proves the theorem for the case of polygonal chains.for the case of bzier curves or biarcs , we consider for each 2-chain p1 , pm , p2 ( with pm being the vertex of degree two ) the triangle =p1pmp2 . lies in a pseudotriangle in which pm has a small angle . due to the affine shape of the faces we use these triangles as control polygons as shown in fig . 13 and replace the 2-chains by bzier curves or biarcs ( similar to lemma 2.1 ) . every plane graph g with n vertices has a plane pointed drawing with either quadratic bzier curves , tangent continuous biarcs , or 2-chains ( polygonal chains consisting of two line segments ) , which uses at most 
 n3 
 non - straight edges . ( otherwise we add edges such that g becomes a triangulation and delete these edges in the end . ) as a first step , we turn g into a combinatorial pointed pseudotriangulation as done in lemma 3.3 . by this we creates four types of bounded faces:(i)triangles,(ii)quadrilaterals with a degree-2 vertex with big angle,(iii)quadrilaterals with a degree-2 vertex with small angle and the big angle is realized next to it,(iv)pentagons with two non - adjacent degree-2 vertices , one of them with a big , one of them with a small angle . we apply the algorithm of   to realize the combinatorial pseudotriangulation . in all faces of type ( iii ) the interior of the triangle spanned by the degree-2 vertex and its two neighbors is empty , see fig . however , the algorithm of   allows us to specify the face shapes up to affine transformations . by giving all faces of type ( iv ) the shape shown in fig . quadrilaterals with a degree-2 vertex with big angle , quadrilaterals with a degree-2 vertex with small angle and the big angle is realized next to it , pentagons with two non - adjacent degree-2 vertices , one of them with a big , one of them with a small angle . what we have obtained so far is a pointed drawing , where at most n3 edges are drawn as 2-chains , which proves the theorem for the case of polygonal chains . for the case of bzier curves or biarcs , we consider for each 2-chain p1 , pm , p2 ( with pm being the vertex of degree two ) the triangle =p1pmp2 . lies in a pseudotriangle in which pm has a small angle . due to the affine shape of the faces we use these triangles as control polygons as shown in fig . 13 and replace the 2-chains by bzier curves or biarcs ( similar to lemma 2.1 ) . in general it is not possible to draw a planar graph pointed using a larger number of ( non - crossing ) straight - line edges , since every maximal pointed straight - line graph has at most 2n3 edges , and due to eulers formula a triangulation has 3n6 edges . in this sense , the big angles of the cpt - assignment and the subdivisions computed by our method are shown in fig . 14(c ) and finally to a pointed drawing with only three bzier curves as shown in fig . 14(d ) . in the proceedings version of this paper , we made a stronger claim [ 1 , theorem 7 ] : for each inner vertex , the face in which it is pointed can be chosen arbitrarily . it is not possible to make the three marked angles big with at most n3 non - straight edges which are either quadratic bzier curves or 2-chains . the reason is that a single quadratic bzier curve bends by less than . therefore , in a triangle with three vertices that are pointed in the interior face , all three edges must be curved , see fig . 15(b ) : if we proceed clockwise along the boundary , the tangent direction turns right by less than  along each edge . at each vertex , it makes a left turn , by pointedness . with less than three curved edges , the tangent direction can not complete a full right turn of 2. the same argument works for 2-chains . by a similar argument , a triangle with two vertices that are pointed in the interior face needs at least two curved edges . applying these facts to our example , we see that all three edges in the triangle abc must be curved . with a total of n=6 vertices , we have thus exhausted our reservoir of at most n3=3 non - straight edges . ac together with the curved edge bc can not make pointed interior angles at b and c in the triangle abc . this example does not rule out the possibility that pointedness in the chosen faces can be achieved with more than n3 curved edges , or with biarcs .
we study the problem how to draw a planar graph crossing - free such that every vertex is incident to an angle greater than . in general a plane straight - line drawing can not guarantee this property . 
 we present algorithms which construct such drawings with either tangent - continuous biarcs or quadratic bzier curves ( parabolic arcs ) , even if the positions of the vertices are predefined by a given plane straight - line drawing of the graph . 
 moreover , the graph can be drawn with circular arcs if the vertices can be placed arbitrarily . 
 the topic is related to non - crossing drawings of multigraphs and vertex labeling .