1428 KB57 KB200820252021García Olaverri, AlfredoPilz, AlexanderTejel Altarriba, Javierštevilka:1letnik:20str. 69-87DOI:10.26493/1855-3974.2226.e93ISSN:1855-3966COBISSID_HOST:91107075URN:URN:NBN:SI:doc-ORYIXTKOenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneagrafgraphNP-complete problemNP-poln problemplane subgraphravninsko vložen podgraftopological drawingtopološka risbaOn plane subgraphs of complete topological drawings|Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings ?$D_n$? of the complete graph ?$K_n$? on ?$n$? vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least ?$\lceil 3 n/2 \rceil$? edges. We also address the problem of obtaining a plane subgraph of ?$D_n$? with the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of ?$D_n$?, a maximum plane augmentation of this subgraph can be found in ?$O(n^3)$? time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-completeTopološke risbe so predstavitve grafov v ravnini, pri katerih so vozlišča grafa predstavljene s točkami v ravnini, povezave pa z enostavnimi krivuljami, ki povezujejo točke. Risba je enostavna, če se dve povezavi sekata kvečjemu v eni točki in to bodisi v skupnem krajiš ču bodisi v pravem presečišču. V tem članku raziskujemo lastnosti maksimalnih ravninsko vloženih podgrafov enostavnih risb ?$D_n$? polnega grafa ?$K_n$? na ?$n$? vozliščih. Naš glavni strukturni rezultat je, da so maksimalni ravninsko vloženi podgrafi 2-povezani, pa tudi, da so, kot smo to poimenovali, bistveno 3-povezavno-povezani. Pokažemo tudi, da vsak maksimalni ravninsko vložen podgraf vsebuje najmanj ?$\lceil 3 n/2 \rceil$? povezav. Obravnavamo tudi problem iskanja ravninsko vloženega podgrafa risbe ?$D_n$? z maksimalnim številom povezav in dokažemo, da je ta problem NP-poln. Kljub temu pa je, če je podan ravninsko vložen vpeti povezani podgraf risbe ?$D_n$?, mogoče najti maksimalno ravninsko razširitev tega podgrafa v času ?$O(n^3)$?. Ob tem pokažemo tudi, da je problem iskanja največjega kompatibilnega ravninsko vloženega grafa z ravnimi črtami, ki ima dve označeni množici vozlišč, NP-polnTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije