Plane triangulations without large 2-trees

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.

Authors

Institutions

Publication Details

Journal
Ars Mathematica Contemporanea
Published
2024-12-13
DOI
https://doi.org/10.26493/1855-3974.3066.5bf
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Plane triangulations without large 2-trees

Allan Bickle, Gunnar Brinkmann
Ars Mathematica Contemporanea
Advanced Graph Theory Research
article

Plane triangulations without large 2-trees

Allan Bickle, Gunnar Brinkmann
article en

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.

Ars Mathematica ContemporaneaVol. 26(1)
Purdue University West Lafayette (US), Ghent University Hospital (BE)
Openalex Percentile: Top 72%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Plane triangulations without large 2-trees — Allan Bickle, Gunnar Brinkmann · Ars Mathematica Contemporanea (2024) | TGRS Research Map | TGRS