Nearly Optimal Visibility Representations of Plane Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Xin He , Huaming Zhang

ABSTRACT

The visibility representation (VR for short) is a classical representation of plane graphs. VR has various applications and has been extensively studied in literature. One of the main focuses of the study is to minimize the size of 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}.In this paper, we prove that every plane graph has a VR with height at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{2n}{3}+2\lceil \sqrt{n/2}\rceil$\end{document}, and a VR with width at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{4n}{3}+2\lceil \sqrt{n}\rceil$\end{document}. These representations are nearly optimal in the sense that they differ from the lower bounds only by a lower order additive term. Both representations can be constructed in linear time. However, the problem of finding VR with optimal height and optimal width simultaneously remains open. More... »

PAGES

407-418

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11786986_36

DOI

http://dx.doi.org/10.1007/11786986_36

DIMENSIONS

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


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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Literary Studies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, SUNY 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": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA", 
          "id": "http://www.grid.ac/institutes/grid.265893.3", 
          "name": [
            "Computer Science Department, 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": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "The visibility representation (VR for short) is a classical representation of plane graphs. VR has various applications and has been extensively studied in literature. One of the main focuses of the study is to minimize the size of 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}.In this paper, we prove that every plane graph has a VR with height 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}$\\frac{2n}{3}+2\\lceil \\sqrt{n/2}\\rceil$\\end{document}, and a VR with width 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}$\\frac{4n}{3}+2\\lceil \\sqrt{n}\\rceil$\\end{document}. These representations are nearly optimal in the sense that they differ from the lower bounds only by a lower order additive term. Both representations can be constructed in linear time. However, the problem of finding VR with optimal height and optimal width simultaneously remains open.", 
    "editor": [
      {
        "familyName": "Bugliesi", 
        "givenName": "Michele", 
        "type": "Person"
      }, 
      {
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "type": "Person"
      }, 
      {
        "familyName": "Sassone", 
        "givenName": "Vladimiro", 
        "type": "Person"
      }, 
      {
        "familyName": "Wegener", 
        "givenName": "Ingo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11786986_36", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-35904-3", 
        "978-3-540-35905-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "representation", 
      "main focus", 
      "sense", 
      "classical representation", 
      "literature", 
      "focus", 
      "linear time", 
      "terms", 
      "paper", 
      "VR", 
      "study", 
      "time", 
      "problem", 
      "graph", 
      "bounds", 
      "applications", 
      "additive term", 
      "height", 
      "size", 
      "lower bounds", 
      "vertices", 
      "width", 
      "optimal height", 
      "optimal width", 
      "graph G", 
      "plane graph", 
      "visibility representation", 
      "size of VR", 
      "plane graph G", 
      "lower order additive term", 
      "order additive term", 
      "Optimal Visibility Representations"
    ], 
    "name": "Nearly Optimal Visibility Representations of Plane Graphs", 
    "pagination": "407-418", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017247286"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11786986_36"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11786986_36", 
      "https://app.dimensions.ai/details/publication/pub.1017247286"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_222.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11786986_36"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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/11786986_36'

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/11786986_36'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11786986_36'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11786986_36'


 

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

117 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11786986_36 schema:about anzsrc-for:20
2 anzsrc-for:2005
3 schema:author N6dd698da0021403e907d30657900cf4f
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description The visibility representation (VR for short) is a classical representation of plane graphs. VR has various applications and has been extensively studied in literature. One of the main focuses of the study is to minimize the size of 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}.In this paper, we prove that every plane graph has a VR with height at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{2n}{3}+2\lceil \sqrt{n/2}\rceil$\end{document}, and a VR with width at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{4n}{3}+2\lceil \sqrt{n}\rceil$\end{document}. These representations are nearly optimal in the sense that they differ from the lower bounds only by a lower order additive term. Both representations can be constructed in linear time. However, the problem of finding VR with optimal height and optimal width simultaneously remains open.
7 schema:editor N2b398c942d5547bc9e890c9ce0151835
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N43226729ec3d43de8ab0a9e0350f0d5d
12 schema:keywords Optimal Visibility Representations
13 VR
14 additive term
15 applications
16 bounds
17 classical representation
18 focus
19 graph
20 graph G
21 height
22 linear time
23 literature
24 lower bounds
25 lower order additive term
26 main focus
27 optimal height
28 optimal width
29 order additive term
30 paper
31 plane graph
32 plane graph G
33 problem
34 representation
35 sense
36 size
37 size of VR
38 study
39 terms
40 time
41 vertices
42 visibility representation
43 width
44 schema:name Nearly Optimal Visibility Representations of Plane Graphs
45 schema:pagination 407-418
46 schema:productId N44c8beb9677c4d639423b8e76bd1f466
47 Neec72b4b40e649e28ed5ffbc3c5510f6
48 schema:publisher Nd0c6cddeb7c542e19aa7c28314825190
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017247286
50 https://doi.org/10.1007/11786986_36
51 schema:sdDatePublished 2021-11-01T18:51
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N4866ee17a1234e549cce543fd1175924
54 schema:url https://doi.org/10.1007/11786986_36
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N02e56894d5cd4393b52a2a9facfda63c schema:familyName Preneel
59 schema:givenName Bart
60 rdf:type schema:Person
61 N2b398c942d5547bc9e890c9ce0151835 rdf:first N928b2ea1b4b648dc9e76b3a899518676
62 rdf:rest Nd4c6320a329e46fda7e3ddf6a1cff6cd
63 N43226729ec3d43de8ab0a9e0350f0d5d schema:isbn 978-3-540-35904-3
64 978-3-540-35905-0
65 schema:name Automata, Languages and Programming
66 rdf:type schema:Book
67 N44c8beb9677c4d639423b8e76bd1f466 schema:name doi
68 schema:value 10.1007/11786986_36
69 rdf:type schema:PropertyValue
70 N4866ee17a1234e549cce543fd1175924 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N676ab63dd41f4db28302ecf7c11fb8ab schema:familyName Sassone
73 schema:givenName Vladimiro
74 rdf:type schema:Person
75 N6dd698da0021403e907d30657900cf4f rdf:first sg:person.011352641523.42
76 rdf:rest N7d6171132dda45028325166dccb15523
77 N7d6171132dda45028325166dccb15523 rdf:first sg:person.012041227127.88
78 rdf:rest rdf:nil
79 N7e86f03609154245a4101b6364357dfa rdf:first N676ab63dd41f4db28302ecf7c11fb8ab
80 rdf:rest Neef1e59fef0b4900af46756c04139fbe
81 N928b2ea1b4b648dc9e76b3a899518676 schema:familyName Bugliesi
82 schema:givenName Michele
83 rdf:type schema:Person
84 Nd0c6cddeb7c542e19aa7c28314825190 schema:name Springer Nature
85 rdf:type schema:Organisation
86 Nd4c6320a329e46fda7e3ddf6a1cff6cd rdf:first N02e56894d5cd4393b52a2a9facfda63c
87 rdf:rest N7e86f03609154245a4101b6364357dfa
88 Ne8f59a29bba94536963b280d36eed97a schema:familyName Wegener
89 schema:givenName Ingo
90 rdf:type schema:Person
91 Neec72b4b40e649e28ed5ffbc3c5510f6 schema:name dimensions_id
92 schema:value pub.1017247286
93 rdf:type schema:PropertyValue
94 Neef1e59fef0b4900af46756c04139fbe rdf:first Ne8f59a29bba94536963b280d36eed97a
95 rdf:rest rdf:nil
96 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
97 schema:name Language, Communication and Culture
98 rdf:type schema:DefinedTerm
99 anzsrc-for:2005 schema:inDefinedTermSet anzsrc-for:
100 schema:name Literary Studies
101 rdf:type schema:DefinedTerm
102 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
103 schema:familyName He
104 schema:givenName Xin
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
106 rdf:type schema:Person
107 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
108 schema:familyName Zhang
109 schema:givenName Huaming
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
111 rdf:type schema:Person
112 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
113 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
114 rdf:type schema:Organization
115 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
116 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
117 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...