| A vertex-face assignment for plane graphs (2008) | |||||||||||||
Abstract | |||||||||||||
| Abstract For any planar straight line graph (Pslg), there is a vertexface assignment such that every vertex is assigned to at most two adjacent faces, and every face is assigned to all its reflex vertices and one more incident vertex. The existence of such an assignment implies, in turn, that any Pslg can be augmented to a connected Pslg such that the degree of every vertex increases by at most two. 1 Introduction A planar straight line graph ( Pslg) partitions the planeinto connected components, which are the faces of the graph. Every Pslg has an unbounded outer face and,if it has circuits, then it also has bounded faces. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||