Article ID Journal Published Year Pages File Type
415847 Computational Geometry 2008 11 Pages PDF
Abstract

Let G be a connected plane geometric graph with n vertices. In this paper, we study bounds on the number of edges required to be added to G to obtain 2-vertex or 2-edge connected plane geometric graphs. In particular, we show that for G to become 2-edge connected, additional edges are required in some cases and that additional edges are always sufficient. For the special case of plane geometric trees, these bounds decrease to and , respectively.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics