Linear-time algorithms for problems on planar graphs with fixed disk dimension

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Langston, Micheal
dc.date.accessioned 2015-12-07T12:33:30Z
dc.date.available 2015-12-07T12:33:30Z
dc.date.copyright 2007
dc.date.issued 2015-12-07
dc.identifier.issn 0020-0190 en_US
dc.identifier.uri http://hdl.handle.net/10725/2777
dc.description.abstract The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are derived, leading to an algorithm to obtain an outerplanar subgraph of a graph with disk dimension k by removing at most 2k−2 vertices. This reduction is used to obtain linear-time exact and approximation algorithms on graphs with fixed disk dimension. In particular, a linear-time approximation algorithm is presented for the pathwidth problem. en_US
dc.language.iso en en_US
dc.title Linear-time algorithms for problems on planar graphs with fixed disk dimension en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Information Processing Letters en_US
dc.journal.volume 101 en_US
dc.journal.issue 1 en_US
dc.article.pages 36-40 en_US
dc.keywords Approximation algorithms en_US
dc.keywords Design of algorithms en_US
dc.keywords Disk dimension en_US
dc.keywords Outerplanar graphs en_US
dc.keywords Pathwidth en_US
dc.keywords Planar graphs en_US
dc.identifier.doi http://dx.doi.org/10.1016/j.ipl.2006.08.006 en_US
dc.identifier.ctation Abu-Khzam, F. N., & Langston, M. A. (2007). Linear-time algorithms for problems on planar graphs with fixed disk dimension. Information processing letters, 101(1), 36-40. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S0020019006002511
dc.orcid.id https://orcid.org/0000-0001-5221-8421

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account