On plane subgraphs of complete topological drawings

angleški

2021

letnik 20, številka 1

graf   NP-poln problem   ravninsko vložen podgraf   topološka risba

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

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.

22.11.2022