Construction Sequences and Certifying 3-Connectedness

Details Construction Sequences and Certifying 3-Connectedness Construction Sequences and Certifying 3-Connectedness

2009-12-14

arxiv.org/abs/0912.2561v2

Computer Science

Data Structures and Algorithms

to be published in STACS 2010

Scientific paper

Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Gruenbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to the K_4 can be computed in O(|V|^2) time by extending Barnette and Gruenbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.

Affiliated with

Also associated with

No associations

Rating

Construction Sequences and Certifying 3-Connectedness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Construction Sequences and Certifying 3-Connectedness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Construction Sequences and Certifying 3-Connectedness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-624048