Convex drawings of the complete graph: topology meets geometry

angleški

2022

letnik 22, številka 3

enostavne risbe   konveksne risbe   polni grafi

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

V geometrijski risbi grafa ?$K_n$?, trivialno vsak 3-cikel omejuje konveksno območje: če sta dva vozlišča v tem območju, potem to velja tudi za (geometrijsko) povezavo med njima. Za topološko risbo ?$D$? grafa ?$K_n$? na sferi rečemo, da je konveksna, če vsak 3-cikel omejuje zaprto območje ?$R$? (na katerikoli od dveh strani 3-cikla), pri tem pa imata poljubna dva vozlišča v ?$R$? (topološko) povezavo med njima vsebovano v ?$R$?. Konveksne risbe po eni strani posplošujejo geometrijske risbe, po drugi strani pa so poddružina topoloških risb. Zato bi bilo lahko presenetljivo, če bi bile vse optimalne (to je, z minimalnim številom presečišč) topološke risbe grafa ?$K_n$? konveksne. Vseeno pa storimo prvi korak k dokazu, da so konveksne: pokažemo, da če ?$D$? vsebuje nekonveksen ?$K_5$?, vse njegove razširitve do ?$K_7$? pa ne vsebujejo nobenega drugega nekonveksnega ?$K_5$?, potem ?$D$? ni optimalen (brez sklicevanja na domnevo o številu presečišč grafa ?$K_n$)?. To je prvi primer netrivialnih lokalnih argumentov, ki dajejo zadostne pogoje za suboptimalnost. Na našo prošnjo je Aichholzer računalniško potrdil, da je, vse do ?$n = 12$?, vsaka optimalna risba grafa ?$K_n$? konveksna. Konveksnost naravno dopušča izpopolnitve, kot sta npr. lastnosti hereditarno konveksen (?$h$?-konveksen) in lično konveksen (?$f$?-konveksen). Hierarhija premočrten ?$\subseteq$? ?$f$?-konveksen ?$\subseteq$? ?$h$?-konveksen ?$\subseteq$? konveksen ?$\subseteq$? topološki opisuje relacije med geometrijskimi in topološkimi risbami. Znano je, da je ?$f$?-konveksnost ekvivalentna psevdolinearnosti (ki posplošuje premočrtnost) in da je ?$h$?-konveksnost ekvivalentna psevdosferičnosti (ki posplošuje sferično geodetskost). Karakteriziramo ?$h$?-konveksnost s tremi prepovedanimi (topološkimi) podrisbami. Ta hierarhija predstavlja okvir za obravnavo posplošitev tudi drugih geometrijskih problemov v zvezi z množicami točk v ravnini. Predstavimo dva primera takšnih problemov, in sicer o številu odprtih trikotnikov ter o obstoju konveksnih ?$k$?-kotnikov.

22.11.2022