Linear-time algorithms for problems on planar graphs with fixed disk dimension
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 w...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| التنسيق: | article |
| منشور في: |
2007
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/2777 http://dx.doi.org/10.1016/j.ipl.2006.08.006 http://www.sciencedirect.com/science/article/pii/S0020019006002511 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513459372163072 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Langston, Micheal |
| author2_role | author |
| author_facet | Abu-Khzam, Faisal N. Langston, Micheal |
| author_role | author |
| dc.contributor.none.fl_str_mv | |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Langston, Micheal |
| dc.date.none.fl_str_mv | 2007 2015-12-07T12:33:30Z 2015-12-07T12:33:30Z 2015-12-07 |
| dc.identifier.none.fl_str_mv | 0020-0190 http://hdl.handle.net/10725/2777 http://dx.doi.org/10.1016/j.ipl.2006.08.006 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. http://www.sciencedirect.com/science/article/pii/S0020019006002511 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Information Processing Letters |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Linear-time algorithms for problems on planar graphs with fixed disk dimension |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_624db1da63011fc963e12f7afb84fb31 |
| identifier_str_mv | 0020-0190 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/2777 |
| publishDate | 2007 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Linear-time algorithms for problems on planar graphs with fixed disk dimensionAbu-Khzam, Faisal N.Langston, MichealThe 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.PublishedN/A2015-12-07T12:33:30Z2015-12-07T12:33:30Z20072015-12-07Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0020-0190http://hdl.handle.net/10725/2777http://dx.doi.org/10.1016/j.ipl.2006.08.006Abu-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.http://www.sciencedirect.com/science/article/pii/S0020019006002511enInformation Processing Lettersinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/27772018-05-21T08:34:21Z |
| spellingShingle | Linear-time algorithms for problems on planar graphs with fixed disk dimension Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Linear-time algorithms for problems on planar graphs with fixed disk dimension |
| title_full | Linear-time algorithms for problems on planar graphs with fixed disk dimension |
| title_fullStr | Linear-time algorithms for problems on planar graphs with fixed disk dimension |
| title_full_unstemmed | Linear-time algorithms for problems on planar graphs with fixed disk dimension |
| title_short | Linear-time algorithms for problems on planar graphs with fixed disk dimension |
| title_sort | Linear-time algorithms for problems on planar graphs with fixed disk dimension |
| url | http://hdl.handle.net/10725/2777 http://dx.doi.org/10.1016/j.ipl.2006.08.006 http://www.sciencedirect.com/science/article/pii/S0020019006002511 |