Width-Optimal Visibility Representations of Plane Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Jia-Hao Fan , Chun-Cheng Lin , Hsueh-I Lu , Hsu-Chun Yen

ABSTRACT

Given an n-node plane graph G, the visibility representation of G is concerned with drawing each node of G using a horizontal line segment such that the line segments associated with any two adjacent nodes of G are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of G no wider than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{4n}{3}\rfloor-2$\end{document}. Our result improves upon the previously known upper bound \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}, providing a positive answer to a conjecture suggested in the literature about whether an upper bound \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} + O(1)$\end{document} on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{4n}{3}\rfloor-3$\end{document} only by one unit. More... »

PAGES

160-171

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-77120-3_16

DOI

http://dx.doi.org/10.1007/978-3-540-77120-3_16

DIMENSIONS

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


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/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": "Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fan", 
        "givenName": "Jia-Hao", 
        "id": "sg:person.012707254057.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012707254057.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Chun-Cheng", 
        "id": "sg:person.010134616271.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010134616271.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Dept. of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, Kainan University, Taoyuan, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.445087.a", 
          "name": [
            "Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC", 
            "Dept. of Computer Science, Kainan University, Taoyuan, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yen", 
        "givenName": "Hsu-Chun", 
        "id": "sg:person.015077575457.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015077575457.09"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "Given an n-node plane graph G, the visibility representation of G is concerned with drawing each node of G using a horizontal line segment such that the line segments associated with any two adjacent nodes of G are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of G no wider than \\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{4n}{3}\\rfloor-2$\\end{document}. Our result improves upon the previously known upper 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}$\\frac{4n}{3}+2\\lceil \\sqrt{n}\\rceil$\\end{document}, providing a positive answer to a conjecture suggested in the literature about whether an upper 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}$\\frac{4n}{3} + O(1)$\\end{document} on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower 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}$\\lfloor\\frac{4n}{3}\\rfloor-3$\\end{document} only by one unit.", 
    "editor": [
      {
        "familyName": "Tokuyama", 
        "givenName": "Takeshi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-77120-3_16", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-77118-0", 
        "978-3-540-77120-3"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "visibility representation", 
      "plane graph", 
      "algorithmic graph theory", 
      "arbitrary plane graphs", 
      "line segments", 
      "plane graph G", 
      "linear time algorithm", 
      "graph theory", 
      "upper bounds", 
      "Compact Visibility Representation", 
      "graph G", 
      "practical interest", 
      "graph", 
      "horizontal line segments", 
      "positive answer", 
      "adjacent nodes", 
      "representation", 
      "theoretical importance", 
      "bounds", 
      "optimality", 
      "conjecture", 
      "theory", 
      "algorithm", 
      "width", 
      "nodes", 
      "fact", 
      "results", 
      "interest", 
      "answers", 
      "literature", 
      "segments", 
      "importance", 
      "units", 
      "attention", 
      "differs", 
      "community", 
      "paper"
    ], 
    "name": "Width-Optimal Visibility Representations of Plane Graphs", 
    "pagination": "160-171", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010193579"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-77120-3_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-77120-3_16", 
      "https://app.dimensions.ai/details/publication/pub.1010193579"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_123.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-77120-3_16"
  }
]
 

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-77120-3_16'

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-77120-3_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-77120-3_16'

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-77120-3_16'


 

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

124 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-77120-3_16 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N7d3eec23549a4a219296066f26639899
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description Given an n-node plane graph G, the visibility representation of G is concerned with drawing each node of G using a horizontal line segment such that the line segments associated with any two adjacent nodes of G are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of G no wider than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{4n}{3}\rfloor-2$\end{document}. Our result improves upon the previously known upper bound \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}, providing a positive answer to a conjecture suggested in the literature about whether an upper bound \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} + O(1)$\end{document} on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{4n}{3}\rfloor-3$\end{document} only by one unit.
7 schema:editor N1f874a5b78414706b5ffd55fab102c7f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf676a6341ceb41f0b73449f134e3ec5f
12 schema:keywords Compact Visibility Representation
13 adjacent nodes
14 algorithm
15 algorithmic graph theory
16 answers
17 arbitrary plane graphs
18 attention
19 bounds
20 community
21 conjecture
22 differs
23 fact
24 graph
25 graph G
26 graph theory
27 horizontal line segments
28 importance
29 interest
30 line segments
31 linear time algorithm
32 literature
33 nodes
34 optimality
35 paper
36 plane graph
37 plane graph G
38 positive answer
39 practical interest
40 representation
41 results
42 segments
43 theoretical importance
44 theory
45 units
46 upper bounds
47 visibility representation
48 width
49 schema:name Width-Optimal Visibility Representations of Plane Graphs
50 schema:pagination 160-171
51 schema:productId N0ef965bce2824fbcb7aa14d2a0e7b792
52 N30898065a85e4337b74faa352c65ee74
53 schema:publisher N005cbdc344114735b771ca22fbe89315
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010193579
55 https://doi.org/10.1007/978-3-540-77120-3_16
56 schema:sdDatePublished 2022-05-20T07:41
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N06a54d04471a49949888a1147d23ae44
59 schema:url https://doi.org/10.1007/978-3-540-77120-3_16
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N005cbdc344114735b771ca22fbe89315 schema:name Springer Nature
64 rdf:type schema:Organisation
65 N06a54d04471a49949888a1147d23ae44 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N06b6dbe6e3fb4eb9a0d6854cabe471e0 schema:familyName Tokuyama
68 schema:givenName Takeshi
69 rdf:type schema:Person
70 N0ef965bce2824fbcb7aa14d2a0e7b792 schema:name doi
71 schema:value 10.1007/978-3-540-77120-3_16
72 rdf:type schema:PropertyValue
73 N1f874a5b78414706b5ffd55fab102c7f rdf:first N06b6dbe6e3fb4eb9a0d6854cabe471e0
74 rdf:rest rdf:nil
75 N30898065a85e4337b74faa352c65ee74 schema:name dimensions_id
76 schema:value pub.1010193579
77 rdf:type schema:PropertyValue
78 N7d3eec23549a4a219296066f26639899 rdf:first sg:person.012707254057.56
79 rdf:rest Ne499db22cef1427b9c342a04a6d9bb25
80 N823b927517904ff89f877ec45c8fa316 rdf:first sg:person.013345515575.46
81 rdf:rest Ne74069e35f7149d39a4ae28104e6f66b
82 Ne499db22cef1427b9c342a04a6d9bb25 rdf:first sg:person.010134616271.54
83 rdf:rest N823b927517904ff89f877ec45c8fa316
84 Ne74069e35f7149d39a4ae28104e6f66b rdf:first sg:person.015077575457.09
85 rdf:rest rdf:nil
86 Nf676a6341ceb41f0b73449f134e3ec5f schema:isbn 978-3-540-77118-0
87 978-3-540-77120-3
88 schema:name Algorithms and Computation
89 rdf:type schema:Book
90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
91 schema:name Mathematical Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
94 schema:name Pure Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.010134616271.54 schema:affiliation grid-institutes:grid.19188.39
97 schema:familyName Lin
98 schema:givenName Chun-Cheng
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010134616271.54
100 rdf:type schema:Person
101 sg:person.012707254057.56 schema:affiliation grid-institutes:grid.19188.39
102 schema:familyName Fan
103 schema:givenName Jia-Hao
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012707254057.56
105 rdf:type schema:Person
106 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
107 schema:familyName Lu
108 schema:givenName Hsueh-I
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
110 rdf:type schema:Person
111 sg:person.015077575457.09 schema:affiliation grid-institutes:grid.445087.a
112 schema:familyName Yen
113 schema:givenName Hsu-Chun
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015077575457.09
115 rdf:type schema:Person
116 grid-institutes:grid.19188.39 schema:alternateName Dept. of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC
117 Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC
118 schema:name Dept. of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC
119 Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC
120 rdf:type schema:Organization
121 grid-institutes:grid.445087.a schema:alternateName Dept. of Computer Science, Kainan University, Taoyuan, Taiwan, ROC
122 schema:name Dept. of Computer Science, Kainan University, Taoyuan, Taiwan, ROC
123 Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, ROC
124 rdf:type schema:Organization
 




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


...