Show simple item record

dc.contributor.authorGolovach, Petr
dc.contributor.authorRequile, Clement
dc.contributor.authorThilikos, Dimitrios M.
dc.PublishedLeibniz International Proceedings in Informatics 2015, 43:30-42eng
dc.description.abstractThe Plane Diameter Completion problem asks, given a plane graph G and a positive integer d, if it is a spanning subgraph of a plane graph H that has diameter at most d. We examine two variants of this problem where the input comes with another parameter k. In the first variant, called BPDC, k upper bounds the total number of edges to be added and in the second, called BFPDC, k upper bounds the number of additional edges per face. We prove that both problems are NP-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when k=1 on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in O(n^{3})+2^{2^{O((kd)^2\log d)}} * n steps.en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY 3.0eng
dc.subjectPlanar graphseng
dc.subjectgraph modification problemseng
dc.subjectparameterized algorithmseng
dc.subjectdynamic programmingeng
dc.titleVariants of plane diameter completionen_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright Petr A. Golovach, Clément Requilé, and Dimitrios M. Thilikosen_US
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution CC BY 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY 3.0