Article ID Journal Published Year Pages File Type
4653855 European Journal of Combinatorics 2012 18 Pages PDF
Abstract

It is shown that every connected planar straight line graph with n≥3n≥3 vertices has an embedding preserving augmentation to a 2-edge connected planar straight line graph with at most ⌊(2n−2)/3⌋⌊(2n−2)/3⌋ new edges. It is also shown that every planar straight line tree with n≥3n≥3 vertices has an embedding preserving augmentation to a 2-edge connected planar topological graph with at most ⌊n/2⌋⌊n/2⌋ new edges. These bounds are the best possible. However, for every n≥3n≥3, there are planar straight line trees with nn vertices that do not have an embedding preserving augmentation to a 2-edge connected planar straight line graph with fewer than 1733n−O(1) new edges.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,