{
"@context": "http://schema.org",
"@type": "ScholarlyArticle",
"@id": "https://doi.org/10.4230/lipics.stacs.2011.141",
"identifier": {
"@type": "PropertyValue",
"propertyID": "DOI",
"value": "https://doi.org/10.4230/lipics.stacs.2011.141"
},
"url": "http://drops.dagstuhl.de/opus/volltexte/2011/3006/",
"additionalType": "ConferencePaper",
"name": "Compact Visibility Representation of Plane Graphs",
"author": [
{
"name": "Jiun-Jie Wang",
"givenName": "Jiun-Jie",
"familyName": "Wang",
"@type": "Person"
},
{
"name": "Xin He",
"givenName": "Xin",
"familyName": "He",
"@type": "Person"
}
],
"editor": {
"name": "Marc Herbstritt",
"givenName": "Marc",
"familyName": "Herbstritt",
"contributorType": "Editor",
"@type": "Person"
},
"description": "The visibility representation (VR for short) is a classical representation of plane graphs. It has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. It is known that there exists a plane graph $G$ with $n$ vertices where any VR of $G$ requires a grid of size at least (2/3)n x((4/3)n-3) (width x height). For upper bounds, it is known that every plane graph has a VR with grid size at most (2/3)n x (2n-5), and a VR with grid size at most (n-1) x (4/3)n. It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely with size at most c_h n x c_w n with c_h < 1 and c_w < 2$).\n\nIn this paper, we provide the first VR construction with this property. We prove that every plane graph of n vertices has a VR with height <= max{23/24 n + 2 Ceil(sqrt(n))+4, 11/12 n + 13} and width <= 23/12 n. The area (height x width) of our VR is larger than the area of some of previous results. However, bounding one dimension of the VR only requires finding a good st-orientation or a good dual s^*t^*-orientation of G. On the other hand, to bound both dimensions of VR simultaneously, one must find a good $st$-orientation and a good dual s^*t^*-orientation at the same time, and thus is far more challenging. Since st-orientation is a very useful concept in other applications, this result may be of independent interests.",
"version": "1.0",
"keywords": "Computer Science, 000 Computer science, knowledge, general works",
"inLanguage": "eng",
"contentSize": "12 pages",
"encodingFormat": "application/pdf",
"datePublished": "2011",
"schemaVersion": "http://datacite.org/schema/kernel-2.1",
"publisher": {
"@type": "Organization",
"name": "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany"
},
"provider": {
"@type": "Organization",
"name": "DataCite"
}
}