Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
415847 | Computational Geometry | 2008 | 11 Pages |
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