Nonseparating Planar Chains in 4-Connected Graphs | Zendy

Sean Curran | Zendy; Orlando Lee | Zendy; Xingxing Yu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Nonseparating Planar Chains in 4-Connected Graphs

Author(s) -

Sean Curran,

Orlando Lee,

Xingxing Yu

Publication year - 2005

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/s0895480103434580

Subject(s) - combinatorics , planar graph , mathematics , planar , planar straight line graph , connected component , graph , connectivity , discrete mathematics , strongly connected component , 1 planar graph , chordal graph , computer science , computer graphics (images)

In this paper, we describe an O(| V (G)E(G)|) algorithm for finding a nonseparating planar chain in a 4-connected graph G, which will be used to decompose an arbitrary 4-connected graph into planar chains. This work was motivated by the study of a multitree approach to reliability in distributed networks, as well as the study of nonseparating induced paths in highly connected graphs

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research