Schmidt, Jens M.Jens M.Schmidt2020-10-232020-10-232010-0327th International Symposium on Theoretical Aspects of Computer Science (2010) 5: 633-644 (2010)http://hdl.handle.net/11420/7652Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grünbaum 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 K4 can be computed in O(|V|2) time by extending Barnette and Grünbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.en3-connectedAlgorithms and data structuresCertifying algorithmConstruction sequenceRemovable edgesTutte contractionConference Paper10.4230/LIPIcs.STACS.2010.2491Other