Plane triangulations without large 2-trees

angleški

2026

letnik 26, številka 1, article p1.03

2-drevo   hamiltonski cikel   triangulacija   Yutsisova particija

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Leta 1995 je Leizhen Cai vprašal, ali ima vsaka ravninska triangulacija razpenjajoče se 2-drevo. Na to vprašanje je nedavno negativno odgovoril Bickle. Podal je ravninsko triangulacijo s 38 vozlišči, za katero vsako 2-drevo, ki je vsebovano v njej, izpusti vsaj eno vozlišče. Mi podamo manjši primer s 29 vozlišči in pokažemo, da za vsako c > 0 obstajajo ravninske triangulacije P = (V, E), tako da vsako 2-drevo, ki je podgraf P , vsebuje manj kot c|V | vozlišč. Podamo tudi spodnjo mejo za velikost največjega 2-drevesa v ravninskih triangulacijah, tako da dokažemo, da vsaka ravninska triangulacija P = (V, E) vsebuje 2-drevo z vsaj log2(|V | - 1) + 4 - log2 3 vozlišči. Nazadnje podamo strukturna merila, ki temeljijo na dekompozicijskih drevesih Jacksona in Yuja, in zagotavljajo obstoj razpenjajočih se 2-dreves v ravninskih triangulacijah. Rezultati so dokazani z uporabo tesne povezave med 2-drevesi, hamiltonskimi cikli in induciranimi drevesi v dualu za ravninske triangulacije brez ločevalnih trikotnikov.

27.10.2026