New Theoretical Bounds of Visibility Representation of Plane Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Huaming Zhang , Xin He

ABSTRACT

In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [6], Tamassia and Tollis [7] independently gave linear time VR algorithms for 2-connected plane graph. Afterwards, one of the main concerns for VR is the size of VR. In this paper, we prove that any plane graph G has a VR with height bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{5n}{6} \rfloor$\end{document}. This improves the previously known bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \frac{15n}{16} \rceil$\end{document}. We also construct a plane graph G with n vertices where any VR of G require a size of \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}. Our result provides an answer to Kant’s open question about whether there exists a plane graph G such that all of its VR require width greater that cn, where c > 1. More... »

PAGES

425-430

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-31843-9_43

DOI

http://dx.doi.org/10.1007/978-3-540-31843-9_43

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": "Zhang", 
        "givenName": "Huaming", 
        "id": "sg:person.012041227127.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
        ], 
        "type": "Person"
      }, 
      {
        "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"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [6], Tamassia and Tollis [7] independently gave linear time VR algorithms for 2-connected plane graph. Afterwards, one of the main concerns for VR is the size of VR. In this paper, we prove that any plane graph G has a VR with height bounded by \\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{5n}{6} \\rfloor$\\end{document}. This improves the previously known bound \\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}$\\lceil \\frac{15n}{16} \\rceil$\\end{document}. We also construct a plane graph G with n vertices where any VR of G require a size of \\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}. Our result provides an answer to Kant\u2019s open question about whether there exists a plane graph G such that all of its VR require width greater that cn, where c > 1.", 
    "editor": [
      {
        "familyName": "Pach", 
        "givenName": "J\u00e1nos", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-31843-9_43", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24528-5", 
        "978-3-540-31843-9"
      ], 
      "name": "Graph Drawing", 
      "type": "Book"
    }, 
    "keywords": [
      "line segments", 
      "graph G", 
      "horizontal line segments", 
      "VR algorithm", 
      "VR", 
      "theoretical bounds", 
      "representation", 
      "plane graph G", 
      "vertices", 
      "adjacent vertices", 
      "vertical line segments", 
      "algorithm", 
      "plane graph", 
      "graph", 
      "main concern", 
      "open question", 
      "new theoretical bounds", 
      "visibility representation", 
      "segments", 
      "Tarjan", 
      "Tamassia", 
      "CN", 
      "bounds", 
      "Rosenstiehl", 
      "concern", 
      "size", 
      "height", 
      "results", 
      "answers", 
      "questions", 
      "width", 
      "paper", 
      "Tollis", 
      "linear time VR algorithms", 
      "time VR algorithms", 
      "size of VR", 
      "Kant\u2019s open question"
    ], 
    "name": "New Theoretical Bounds of Visibility Representation of Plane Graphs", 
    "pagination": "425-430", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003846466"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-31843-9_43"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-31843-9_43", 
      "https://app.dimensions.ai/details/publication/pub.1003846466"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:54", 
    "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_279.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-31843-9_43"
  }
]
 

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/978-3-540-31843-9_43'

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-540-31843-9_43'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-31843-9_43'

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-540-31843-9_43'


 

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

104 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-31843-9_43 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Ne4330210488a4f6abda5e5b00fdc11f6
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [6], Tamassia and Tollis [7] independently gave linear time VR algorithms for 2-connected plane graph. Afterwards, one of the main concerns for VR is the size of VR. In this paper, we prove that any plane graph G has a VR with height bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor \frac{5n}{6} \rfloor$\end{document}. This improves the previously known bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lceil \frac{15n}{16} \rceil$\end{document}. We also construct a plane graph G with n vertices where any VR of G require a size of \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}. Our result provides an answer to Kant’s open question about whether there exists a plane graph G such that all of its VR require width greater that cn, where c > 1.
7 schema:editor Ndfe6a94187de420897ad840b5b431436
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na368a2f318514cec9dd3282d685c4cee
12 schema:keywords CN
13 Kant’s open question
14 Rosenstiehl
15 Tamassia
16 Tarjan
17 Tollis
18 VR
19 VR algorithm
20 adjacent vertices
21 algorithm
22 answers
23 bounds
24 concern
25 graph
26 graph G
27 height
28 horizontal line segments
29 line segments
30 linear time VR algorithms
31 main concern
32 new theoretical bounds
33 open question
34 paper
35 plane graph
36 plane graph G
37 questions
38 representation
39 results
40 segments
41 size
42 size of VR
43 theoretical bounds
44 time VR algorithms
45 vertical line segments
46 vertices
47 visibility representation
48 width
49 schema:name New Theoretical Bounds of Visibility Representation of Plane Graphs
50 schema:pagination 425-430
51 schema:productId N3ea34ec6cdf54bf1a950767ec143becb
52 N6419c540c3cb4d7c9a11d9809a07fdc7
53 schema:publisher N0cb7ab8319f8417eb29043e3d354df89
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003846466
55 https://doi.org/10.1007/978-3-540-31843-9_43
56 schema:sdDatePublished 2021-11-01T18:54
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher Ne3c53805f4f34bf2bfbda2a0f3383070
59 schema:url https://doi.org/10.1007/978-3-540-31843-9_43
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N0cb7ab8319f8417eb29043e3d354df89 schema:name Springer Nature
64 rdf:type schema:Organisation
65 N16ddd287028644e6af07f5694b534a4c rdf:first sg:person.011352641523.42
66 rdf:rest rdf:nil
67 N3ea34ec6cdf54bf1a950767ec143becb schema:name doi
68 schema:value 10.1007/978-3-540-31843-9_43
69 rdf:type schema:PropertyValue
70 N6419c540c3cb4d7c9a11d9809a07fdc7 schema:name dimensions_id
71 schema:value pub.1003846466
72 rdf:type schema:PropertyValue
73 Na368a2f318514cec9dd3282d685c4cee schema:isbn 978-3-540-24528-5
74 978-3-540-31843-9
75 schema:name Graph Drawing
76 rdf:type schema:Book
77 Ndb020e6ba0f44127bbd602becc67ab4f schema:familyName Pach
78 schema:givenName János
79 rdf:type schema:Person
80 Ndfe6a94187de420897ad840b5b431436 rdf:first Ndb020e6ba0f44127bbd602becc67ab4f
81 rdf:rest rdf:nil
82 Ne3c53805f4f34bf2bfbda2a0f3383070 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Ne4330210488a4f6abda5e5b00fdc11f6 rdf:first sg:person.012041227127.88
85 rdf:rest N16ddd287028644e6af07f5694b534a4c
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
90 schema:name Artificial Intelligence and Image Processing
91 rdf:type schema:DefinedTerm
92 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
93 schema:familyName He
94 schema:givenName Xin
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
96 rdf:type schema:Person
97 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.273335.3
98 schema:familyName Zhang
99 schema:givenName Huaming
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
101 rdf:type schema:Person
102 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
103 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
104 rdf:type schema:Organization
 




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


...