Given a graph G, let a k-trestle of G be a 2-connected spanning subgra
ph of G of maximum degree at most k. Also, let chi(G) be the Euler cha
racteristic of G. This paper shows that every 3-connected graph G has
a (10-2 chi(G))-trestle. If chi(G)less than or equal to -5, this is im
proved to 8-2 chi(G), and for chi(G)less than or equal to -10, this is
further improved to 6-2 chi(G). This result is shown to be best possi
ble for almost all values of chi(G) by the demonstration of 3-connecte
d graphs embedded on each surface of Euler characteristic chi less tha
n or equal to 0 which have no (5-2 chi)-trestle. Also, it is shown tha
t a 4-connected graph embeddable on a surface with non-negative Euler
characteristic has a 3-trestle, approaching a conjecture of Nash-Willi
ams. (C) 1998 Academic Press.