Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10104307" target="_blank" >RIV/00216208:11320/11:10104307 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s00453-011-9551-0" target="_blank" >http://dx.doi.org/10.1007/s00453-011-9551-0</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00453-011-9551-0" target="_blank" >10.1007/s00453-011-9551-0</a>

Result language
angličtina
Original language name
Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three
Original language description
We characterize the planar straight line graphs (Pslgs) that can be augmented to 3-connected and 3-edge-connected Pslgs, respectively. We show that if a Pslg with n vertices can be augmented to a 3-edge-connected Pslg, then at most 2n-2 new edges are always sufficient and sometimes necessary for the augmentation. If the input Pslg is, in addition, already 2-edge-connected, then n-2 new edges are always sufficient and sometimes necessary for the augmentation to a 3-edge-connected Pslg.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BD - Information theory
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)