Plane triangulations without large 2-treesBickle, Allan (Avtor) Brinkmann, Gunnar (Avtor) 2-treetriangulationHamiltonian cycleYutsis partitionIn 1995 Leizhen Cai asked whether each plane triangulation has a spanning 2-tree. This question was recently answered in the negative by Bickle. He gave a plane triangulation on 38 vertices for which each 2-tree contained in it misses at least one vertex. We give a smaller example on 29 vertices and show that for each c>0 there are plane triangulations P=(V,E), so that each 2-tree that is a subgraph of P contains fewer than c|V| vertices. We also give a lower bound for the size of a maximum 2-tree in plane triangulations by proving that each plane triangulation P=(V,E) contains a 2-tree on at least log_2 (|V|-1)+4 -log_2 3 vertices. Finally we give structural criteria based on the decomposition trees of Jackson and Yu that guarantee the existence of spanning 2-trees in plane triangulations. The results are proven by using the close relation of 2-trees to hamiltonian cycles and to induced trees in the dual for plane triangulations without separating triangles.Založba Univerze na Primorskem20262025-12-21 22:15:55Članek v reviji22287UDK: 51eISSN: 1855-3974DOI: 10.26493/1855-3974.3066.5bfsl