On the disk dimension of planar graphs

LAUR Repository

Show simple item record

dc.contributor.author Abu-khzam, Faisal
dc.date.accessioned 2018-04-26T07:19:29Z
dc.date.available 2018-04-26T07:19:29Z
dc.date.copyright 2011 en_US
dc.date.issued 2018-04-26
dc.identifier.uri http://hdl.handle.net/10725/7596
dc.description.abstract The disk dimension problem was introduced by Fellows and Langston in 1987. The disk dimension of a graph, G, is the least k for which G embeds in the plane minus k open disks, with every vertex of G on a boundary of one of the disks. Disk dimension finds application in circuit layout and related fields. For every fixed k, the family of ``yes'' instances is closed under minors and excludes a planar graph. Thus graphs of disk dimension k or less are in principle (but not constructively) recognizable in linear time. In this paper, we study instead constructive techniques to decide the disk dimension problem. We prove that a graph of disk dimension k has treewidth at most 2k, and is thus amenable to an approach based on dynamic programming for fixed-width tree decompositions. More significantly, we devise a direct and highly practical linear-time algorithm to decide whether an arbitrary graph has fixed disk dimension k or less. We also discuss it's efficiency and implementation. Finally we investigate the pathwidth approximation strategy proposed for outerplanar graphs by Govindan, Langston and Yan in 1998. We demonstrate that it can be used in this setting to obtain a practical, linear-time pathwidth heuristic for graphs of bounded disk dimension. We prove that this fast heuristic, when given a graph of pathwidth p and fixed disk dimension k, will produce a path decomposition whose width is at most 3p+2k-2. en_US
dc.language.iso en en_US
dc.title On the disk dimension of planar graphs en_US
dc.type Conference Paper / Proceeding 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.identifier.ctation Abu-Khzam, F. On the Disk Dimension of Planar Graphs Horizons in Combinatorics.16th Shanks Lecture Series. May 21-24, 2001.Vanderbilt University.Nashville, TN, USA en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date May 21-24, 2001 en_US
dc.conference.place Nashville, TN, USA en_US
dc.conference.title Horizons in Combinatorics/16th Shanks Lecture Series en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url http://at.yorku.ca/c/a/g/s/70.htm en_US
dc.orcid.id https://orcid.org/0000-0001-5221-8421 en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account