@article{01KEH0YRJEDY17F84Z0E808VR9,
  abstract     = {{In 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.}},
  articleno    = {{P103}},
  author       = {{Bickle, Allan and Brinkmann, Gunnar}},
  issn         = {{1855-3966}},
  journal      = {{ARS MATHEMATICA CONTEMPORANEA}},
  keywords     = {{2-tree,triangulation,Hamiltonian cycle,Yutsis partition,CYCLES}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{15}},
  title        = {{Plane triangulations without large 2-trees}},
  url          = {{http://doi.org/10.26493/1855-3974.3066.5bf}},
  volume       = {{26}},
  year         = {{2026}},
}

Altmetric

View in Altmetric

Web of Science

Times cited: