523 KB81 KB200820252022Arroyo, AlanMcQuillan, DanRichter, R. BruceSalazar, Gelasioletnik:22številka:3P3.04 (27 str.)DOI:10.26493/1855-3974.2134.ac9COBISSID_HOST:117983491ISSN:1855-3966URN:URN:NBN:SI:doc-EK0G70ZFenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneacomplete graphsconvex drawingsenostavne risbekonveksne risbepolni grafisimple drawingsConvex drawings of the complete graph: topology meets geometry|In a geometric drawing of ?$K_n$?, trivially each 3-cycle bounds a convex region: if two vertices are in that region, then so is the (geometric) edge between them. We define a topological drawing ?$D$? of ?$K_n$? to be convex if each 3-cycle bounds a closed region ?$R$? such that any two vertices in ?$R$? have the (topological) edge between them contained in ?$R$?. While convex drawings generalize geometric drawings, they specialize topological ones. Therefore it might be surprising if all optimal (that is, crossing-minimal) topological drawings of ?$K_n$? were convex. However, we take a first step to showing that they are convex: we show that if ?$D$? has a non-convex ?$K_5$? all of whose extensions to a ?$K_7$? have no other non-convex ?$K_5$?, then ?$D$? is not optimal (without reference to the conjecture for the crossing number of ?$K_n$?). This is the first example of non-trivial local considerations providing sufficient conditions for suboptimality. At our request, Aichholzer has computationally verified that, up to ?$n = 12$?, every optimal drawing of ?$K_n$? is convex. Convexity naturally lends itself to refinements, including hereditarily convex (?$h$?-convex) and face convex (?$f$?-convex). The hierarchy rectilinear ?$\subseteq$? ?$f$?-convex ?$\subseteq$? ?$h$?-convex ?$\subseteq$? convex ?$\subseteq$? topological provides links between geometric and topological drawings. It is known that ?$f$?-convex is equivalent to pseudolinear (generalizing rectilinear) and ?$h$?-convex is equivalent to pseudospherical (generalizing spherical geodesic). We characterize ?$h$?-convexity by three forbidden (topological) subdrawings. This hierarchy provides a framework to consider generalizations of other geometric questions for point sets in the plane. We provide two examples of such questions, namely numbers of empty triangles and existence of convex ?$k$?-gonsV 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$?-kotnikovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije