Faces in the crowd

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Langston, Micheal A.
dc.date.accessioned 2017-03-22T11:40:17Z
dc.date.available 2017-03-22T11:40:17Z
dc.date.issued 2017-03-22
dc.identifier.uri http://hdl.handle.net/10725/5413
dc.description.abstract We study a pair of N P-hard problems aimed at finding small sets of faces in planar graphs. In the disk dimension problem, we are given a planar graph G, and seek the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary ofsome disk. Useful properties of graphs with bounded disk dimension are derived. We show how to obtain an outerplanar subgraph of a graph of disk dimension k by removing at most 2k − 2 vertices. We use this reduction technique to obtain a tree-decomposition of width at most 2k and a linear-time 3-approximation algorithm for the pathwidth problem on graphs of fixed disk dimension. Such results were previously known only for outerplanar graphs (graphs of disk dimension one). In the related face cover problem, we are given a plane graph G, and seek the least number k of faces whose boundaries contain all the vertices of G. Although both problems are FPT, we are able to exploit the embedding that comes with face cover instances to deriva direct O(5k + N2) algorithm, where N is the input size. This is a considerable improvement over the best previously-published face cover algorithms, which rely instead on reductions to planar dominating set. en_US
dc.language.iso en en_US
dc.title Faces in the crowd en_US
dc.type Conference Paper / Proceeding en_US
dc.title.subtitle on the algorithmic utility of disks and covers en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url http://web.eecs.utk.edu/~langston/projects/papers/dd-and-fc.pdf en_US
dc.orcid.id https://orcid.org/0000-0001-5221-8421
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account