Abstrakt. Paret (G, D) bestående av en planar graf G V, E) med n hörn tillsammans med en delmängd av d speciella hörn D V kallas k-planar om det finns en inbäddning av G i planet så att som mest k ansikten av G krävs för att täcka alla hörn i D. Kontroll 1-plan kan göras i linjär tid eftersom det minskar till ett problem att kontrollera planaritet av en relaterad graf. Vi presenterar en algoritm som ger en graf G och ett värde k antingen bestämmer att G inte är k-planar eller genererar en lämplig inbäddning och tillhörande minimal täckning i O (ckn) tid, där c är en konstant. Därför, algoritmen körs i linjär tid för varje fast k. Det faktum att den tid som krävs av algoritmen växer exponentiellt i k är att vänta eftersom vi också visar att för godtycklig k, är tillhörande beslutsproblem starkt NP-komplett, även när planar grafen har i huvudsak en unik planar inbäddning, d 0 (n), och alla ansiktscykler har avgränsad längd. Dessa resultat ger en polynom-tidsigenkänningsalgoritm för speciella fall av Steiner trädproblem i grafer som kan lösas i polynom tid.
Eftersom en ritning och en terminal uppsättning K, γ(G, K) kunde hittas i polynom tid REF.
On the Complexity of Covering Vertices by Faces in a Planar Graph
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}