On plane subgraphs of complete topological drawings - García Olaverri, Alfredo (Ars mathematica contemporanea, 2021)
Topološ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-poln.
Keywords: graf; graph; NP-complete problem; NP-poln problem; plane subgraph; ravninsko vložen podgraf; topological drawing; topološka risba