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": "2022-01-01T19:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_296.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 Nbf8dbdd3933e4cd2bf56fc91947a651c
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 Nc0a73f7f3eb3458d90e3351cef668071
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb1a71918fbbf404b8de36de30f38a2b7
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 Nb419ea75dc714299a3de93fba3aaee38
47 Ndbbc6df802a84ba386067d93df5acb25
48 schema:publisher N047e9f4470a14f9b8afb209e2b004a7d
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017247286
50 https://doi.org/10.1007/11786986_36
51 schema:sdDatePublished 2022-01-01T19:17
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Ne594e624f07d422cae7898bbe9ee582b
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 N047e9f4470a14f9b8afb209e2b004a7d schema:name Springer Nature
59 rdf:type schema:Organisation
60 N110fdf9af2214977baca70c4ff575c8d rdf:first N1b3404c620544e2495b4f5f0ad58010c
61 rdf:rest N69dffdfd26ef4bc89aaf756cb7fa07d2
62 N1a8f3490dc5e4e63b54d265fee513dc1 rdf:first sg:person.012041227127.88
63 rdf:rest rdf:nil
64 N1b3404c620544e2495b4f5f0ad58010c schema:familyName Preneel
65 schema:givenName Bart
66 rdf:type schema:Person
67 N69dffdfd26ef4bc89aaf756cb7fa07d2 rdf:first N7c0c1a003d854d6781780dfe03521ce6
68 rdf:rest Na6f675bcc07b47c58d86181ae13e4c61
69 N7c0c1a003d854d6781780dfe03521ce6 schema:familyName Sassone
70 schema:givenName Vladimiro
71 rdf:type schema:Person
72 Na6f675bcc07b47c58d86181ae13e4c61 rdf:first Ne904950d3340440aa8d5d1947958c6ef
73 rdf:rest rdf:nil
74 Nb1a71918fbbf404b8de36de30f38a2b7 schema:isbn 978-3-540-35904-3
75 978-3-540-35905-0
76 schema:name Automata, Languages and Programming
77 rdf:type schema:Book
78 Nb419ea75dc714299a3de93fba3aaee38 schema:name dimensions_id
79 schema:value pub.1017247286
80 rdf:type schema:PropertyValue
81 Nbf8dbdd3933e4cd2bf56fc91947a651c rdf:first sg:person.011352641523.42
82 rdf:rest N1a8f3490dc5e4e63b54d265fee513dc1
83 Nc03eac2d7dee44d69db0c861bdbd4e2e schema:familyName Bugliesi
84 schema:givenName Michele
85 rdf:type schema:Person
86 Nc0a73f7f3eb3458d90e3351cef668071 rdf:first Nc03eac2d7dee44d69db0c861bdbd4e2e
87 rdf:rest N110fdf9af2214977baca70c4ff575c8d
88 Ndbbc6df802a84ba386067d93df5acb25 schema:name doi
89 schema:value 10.1007/11786986_36
90 rdf:type schema:PropertyValue
91 Ne594e624f07d422cae7898bbe9ee582b schema:name Springer Nature - SN SciGraph project
92 rdf:type schema:Organization
93 Ne904950d3340440aa8d5d1947958c6ef schema:familyName Wegener
94 schema:givenName Ingo
95 rdf:type schema:Person
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)


...