# Compact Visibility Representation of 4-Connected Plane Graphs

Ontology type: schema:Chapter

### Chapter Info

DATE

2010

AUTHORS ABSTRACT

The visibility representation (VR for short) is a classical representation of plane graphs. The VR 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 size at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{2n}{3} \rfloor \times (\lfloor \frac{4n}{3} \rfloor -3)$\end{document}. For upper bounds, it is known that every plane graph has a VR with size at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{2}{3}n \rfloor \times (2n-5)$\end{document}, and a VR with size at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(n-1) \times \lfloor \frac{4}{3}n \rfloor$\end{document}.It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely of size chn ×cwn with ch< 1 and cw< 2). In this paper, we provide the first VR construction for a non-trivial graph class that simultaneously bounds both the height and the width. We prove that every 4-connected plane graph has a VR with height \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\leq \frac{3n}{4}+2\lceil\sqrt{n}\rceil +4$\end{document} and width \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\leq \lceil \frac{3n}{2}\rceil$\end{document}. Our VR algorithm is based on an st-orientation of 4-connected plane graphs with special properties. Since the st-orientation is a very useful concept in other applications, this result may be of independent interests. More... »

PAGES

339-353

### Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-642-17457-5
978-3-642-17458-2

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-17458-2_28

DOI

http://dx.doi.org/10.1007/978-3-642-17458-2_28

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1032569292

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, University at Buffalo, 14260, Buffalo, NY, USA",
"id": "http://www.grid.ac/institutes/grid.273335.3",
"name": [
"Department of Computer Science and Engineering, University at Buffalo, 14260, Buffalo, NY, USA"
],
"type": "Organization"
},
"familyName": "He",
"givenName": "Xin",
"id": "sg:person.011352641523.42",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, University at Buffalo, 14260, Buffalo, NY, USA",
"id": "http://www.grid.ac/institutes/grid.273335.3",
"name": [
"Department of Computer Science and Engineering, University at Buffalo, 14260, Buffalo, NY, USA"
],
"type": "Organization"
},
"familyName": "Wang",
"givenName": "Jiun-Jie",
"id": "sg:person.016466617610.57",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016466617610.57"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Alabama in Huntsville, 35899, Huntsville, AL, USA",
"id": "http://www.grid.ac/institutes/grid.265893.3",
"name": [
"Department of Computer Science, University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
],
"type": "Organization"
},
"familyName": "Zhang",
"givenName": "Huaming",
"id": "sg:person.012041227127.88",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
],
"type": "Person"
}
],
"datePublished": "2010",
"datePublishedReg": "2010-01-01",
"description": "The visibility representation (VR for short) is a classical representation of plane graphs. The VR 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 size at least \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\lfloor \\frac{2n}{3} \\rfloor \\times (\\lfloor \\frac{4n}{3} \\rfloor -3)$\\end{document}. For upper bounds, it is known that every plane graph has a VR with size at most \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\lfloor \\frac{2}{3}n \\rfloor \\times (2n-5)$\\end{document}, and a VR with size at most \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$(n-1) \\times \\lfloor \\frac{4}{3}n \\rfloor$\\end{document}.It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely of size chn \u00d7cwn with ch<\u20091 and cw<\u20092). In this paper, we provide the first VR construction for a non-trivial graph class that simultaneously bounds both the height and the width. We prove that every 4-connected plane graph has a VR with height \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\leq \\frac{3n}{4}+2\\lceil\\sqrt{n}\\rceil +4$\\end{document} and width \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\leq \\lceil \\frac{3n}{2}\\rceil$\\end{document}. Our VR algorithm is based on an st-orientation of 4-connected plane graphs with special properties. Since the st-orientation is a very useful concept in other applications, this result may be of independent interests.",
"editor": [
{
"familyName": "Wu",
"givenName": "Weili",
"type": "Person"
},
{
"familyName": "Daescu",
"givenName": "Ovidiu",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-17458-2_28",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-17457-5",
"978-3-642-17458-2"
],
"name": "Combinatorial Optimization and Applications",
"type": "Book"
},
"keywords": [
"study",
"VR",
"size",
"height",
"focus",
"results",
"main focus",
"interest",
"class",
"useful concept",
"problem",
"width",
"applications",
"properties",
"concept",
"representation",
"special properties",
"graph G",
"vertices",
"paper",
"construction",
"algorithm",
"graph",
"classical representation",
"upper bounds",
"plane graph",
"bounds",
"open problem",
"trivial upper bounds",
"graph classes",
"independent interest",
"visibility representation",
"plane graph G",
"VR algorithm",
"first VR construction",
"VR construction",
"non-trivial graph class",
"Compact Visibility Representation"
],
"name": "Compact Visibility Representation of 4-Connected Plane Graphs",
"pagination": "339-353",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1032569292"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-17458-2_28"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-17458-2_28",
"https://app.dimensions.ai/details/publication/pub.1032569292"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:53",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_269.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-17458-2_28"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17458-2_28'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17458-2_28'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17458-2_28'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17458-2_28'

This table displays all metadata directly associated to this object as RDF triples.

120 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
3 schema:author Nfb3691dc4aac4241afb369780b7d06d1
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description The visibility representation (VR for short) is a classical representation of plane graphs. The VR 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 size at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{2n}{3} \rfloor \times (\lfloor \frac{4n}{3} \rfloor -3)$\end{document}. For upper bounds, it is known that every plane graph has a VR with size at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{2}{3}n \rfloor \times (2n-5)$\end{document}, and a VR with size at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(n-1) \times \lfloor \frac{4}{3}n \rfloor$\end{document}.It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely of size chn ×cwn with ch< 1 and cw< 2). In this paper, we provide the first VR construction for a non-trivial graph class that simultaneously bounds both the height and the width. We prove that every 4-connected plane graph has a VR with height \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\leq \frac{3n}{4}+2\lceil\sqrt{n}\rceil +4$\end{document} and width \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\leq \lceil \frac{3n}{2}\rceil$\end{document}. Our VR algorithm is based on an st-orientation of 4-connected plane graphs with special properties. Since the st-orientation is a very useful concept in other applications, this result may be of independent interests.
7 schema:editor N85c959ccd69a4a338cacc7b6cabd7ee6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9b7ba6c272444af0ae908157b883a076
12 schema:keywords Compact Visibility Representation
13 VR
14 VR algorithm
15 VR construction
16 algorithm
17 applications
18 bounds
19 class
20 classical representation
21 concept
22 construction
23 first VR construction
24 focus
25 graph
26 graph G
27 graph classes
28 height
29 independent interest
30 interest
31 main focus
32 non-trivial graph class
33 open problem
34 paper
35 plane graph
36 plane graph G
37 problem
38 properties
39 representation
40 results
41 size
42 special properties
43 study
44 trivial upper bounds
45 upper bounds
46 useful concept
47 vertices
48 visibility representation
49 width
50 schema:name Compact Visibility Representation of 4-Connected Plane Graphs
51 schema:pagination 339-353
52 schema:productId N16c5fb6d99224f4091dc62e7e925e69a
53 Nb75ab581aff6454f86350bf945050748
54 schema:publisher N8183828ffda44836a80d8d7a97db0fd4
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032569292
56 https://doi.org/10.1007/978-3-642-17458-2_28
57 schema:sdDatePublished 2021-11-01T18:53
59 schema:sdPublisher N68aab15a0b604468a818b5c24dbee356
60 schema:url https://doi.org/10.1007/978-3-642-17458-2_28
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
65 schema:givenName Ovidiu
66 rdf:type schema:Person
67 N14a60dca72444ecf9c49158277232afe schema:familyName Wu
68 schema:givenName Weili
69 rdf:type schema:Person
70 N16c5fb6d99224f4091dc62e7e925e69a schema:name dimensions_id
71 schema:value pub.1032569292
72 rdf:type schema:PropertyValue
74 rdf:rest rdf:nil
75 N68aab15a0b604468a818b5c24dbee356 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N8183828ffda44836a80d8d7a97db0fd4 schema:name Springer Nature
78 rdf:type schema:Organisation
79 N85c959ccd69a4a338cacc7b6cabd7ee6 rdf:first N14a60dca72444ecf9c49158277232afe
80 rdf:rest N62863346214648baa3e5081a16845729
81 N9b7ba6c272444af0ae908157b883a076 schema:isbn 978-3-642-17457-5
82 978-3-642-17458-2
83 schema:name Combinatorial Optimization and Applications
84 rdf:type schema:Book
85 N9c3a3231a88945faae02755832eddf1e rdf:first sg:person.012041227127.88
86 rdf:rest rdf:nil
87 Nb75ab581aff6454f86350bf945050748 schema:name doi
88 schema:value 10.1007/978-3-642-17458-2_28
89 rdf:type schema:PropertyValue
90 Nd17f825f97154411b603a9074019e0d7 rdf:first sg:person.016466617610.57
91 rdf:rest N9c3a3231a88945faae02755832eddf1e
92 Nfb3691dc4aac4241afb369780b7d06d1 rdf:first sg:person.011352641523.42
93 rdf:rest Nd17f825f97154411b603a9074019e0d7
94 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
95 schema:name Mathematical Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
98 schema:name Pure Mathematics
99 rdf:type schema:DefinedTerm
100 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
101 schema:familyName He
102 schema:givenName Xin
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
104 rdf:type schema:Person
105 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
106 schema:familyName Zhang
107 schema:givenName Huaming
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
109 rdf:type schema:Person
110 sg:person.016466617610.57 schema:affiliation grid-institutes:grid.273335.3
111 schema:familyName Wang
112 schema:givenName Jiun-Jie
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016466617610.57
114 rdf:type schema:Person
115 grid-institutes:grid.265893.3 schema:alternateName Department of Computer Science, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
116 schema:name Department of Computer Science, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
117 rdf:type schema:Organization
118 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, University at Buffalo, 14260, Buffalo, NY, USA
119 schema:name Department of Computer Science and Engineering, University at Buffalo, 14260, Buffalo, NY, USA
120 rdf:type schema:Organization