Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Chieh-Yu Chen , Ya-Fei Hung , Hsueh-I Lu

ABSTRACT

A visibility representation of a graph G is to represent the nodes of G with non-overlapping horizontal line segments such that the line segments representing any two distinct adjacent nodes are vertically visible to each other. If G is a plane graph, i.e., a planar graph equipped with a planar embedding, a visibility representation of G has the additional requirement of reflecting the given planar embedding of G. For the case that G is an n-node four-connected plane graph, we give an O(n)-time algorithm to produce a visibility representation of G 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} $\left\lceil\frac{n}{2}\right\rceil+2\left\lceil\sqrt{\frac{n-2}{2}}\right\rceil$ \end{document}. To ensure that the first-order term of the upper bound is optimal, we also show an n-node four-connected plane graph G, for infinite number of n, whose visibility representations require heights at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\frac{n}{2}$ \end{document}. More... »

PAGES

67-77

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-00219-9_8

DOI

http://dx.doi.org/10.1007/978-3-642-00219-9_8

DIMENSIONS

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


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": "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Chieh-Yu", 
        "id": "sg:person.011752554575.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011752554575.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graduate Institute of Networking and Multimedia, National Taiwan University, 1 Roosevelt Road, Section 4, Taipei 106, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Graduate Institute of Networking and Multimedia, National Taiwan University, 1 Roosevelt Road, Section 4, Taipei 106, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hung", 
        "givenName": "Ya-Fei", 
        "id": "sg:person.012550135175.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012550135175.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graduate Institute of Networking and Multimedia, National Taiwan University, 1 Roosevelt Road, Section 4, Taipei 106, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan", 
            "Graduate Institute of Networking and Multimedia, National Taiwan University, 1 Roosevelt Road, Section 4, Taipei 106, 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"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "A visibility representation of a graph G is to represent the nodes of G with non-overlapping horizontal line segments such that the line segments representing any two distinct adjacent nodes are vertically visible to each other. If G is a plane graph, i.e., a planar graph equipped with a planar embedding, a visibility representation of G has the additional requirement of reflecting the given planar embedding of G. For the case that G is an n-node four-connected plane graph, we give an O(n)-time algorithm to produce a visibility representation of G 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}\n$\\left\\lceil\\frac{n}{2}\\right\\rceil+2\\left\\lceil\\sqrt{\\frac{n-2}{2}}\\right\\rceil$\n\\end{document}. To ensure that the first-order term of the upper bound is optimal, we also show an n-node four-connected plane graph G, for infinite number of n, whose visibility representations require heights 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}\n$\\frac{n}{2}$\n\\end{document}.", 
    "editor": [
      {
        "familyName": "Tollis", 
        "givenName": "Ioannis G.", 
        "type": "Person"
      }, 
      {
        "familyName": "Patrignani", 
        "givenName": "Maurizio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-00219-9_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-00218-2", 
        "978-3-642-00219-9"
      ], 
      "name": "Graph Drawing", 
      "type": "Book"
    }, 
    "keywords": [
      "visibility representation", 
      "planar embedding", 
      "plane graph", 
      "graph G", 
      "first-order terms", 
      "line segments", 
      "plane graph G", 
      "infinite number", 
      "planar graphs", 
      "time algorithm", 
      "graph", 
      "horizontal line segments", 
      "adjacent nodes", 
      "representation", 
      "optimal height", 
      "embedding", 
      "additional requirements", 
      "algorithm", 
      "nodes", 
      "terms", 
      "four", 
      "number", 
      "height", 
      "cases", 
      "requirements", 
      "segments"
    ], 
    "name": "Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights", 
    "pagination": "67-77", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047130880"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-00219-9_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-00219-9_8", 
      "https://app.dimensions.ai/details/publication/pub.1047130880"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_392.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-00219-9_8"
  }
]
 

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-642-00219-9_8'

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-00219-9_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00219-9_8'

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-00219-9_8'


 

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

107 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-00219-9_8 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N641719bdb52349b1a70dfdf64ada6bc7
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description A visibility representation of a graph G is to represent the nodes of G with non-overlapping horizontal line segments such that the line segments representing any two distinct adjacent nodes are vertically visible to each other. If G is a plane graph, i.e., a planar graph equipped with a planar embedding, a visibility representation of G has the additional requirement of reflecting the given planar embedding of G. For the case that G is an n-node four-connected plane graph, we give an O(n)-time algorithm to produce a visibility representation of G 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} $\left\lceil\frac{n}{2}\right\rceil+2\left\lceil\sqrt{\frac{n-2}{2}}\right\rceil$ \end{document}. To ensure that the first-order term of the upper bound is optimal, we also show an n-node four-connected plane graph G, for infinite number of n, whose visibility representations require heights at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\frac{n}{2}$ \end{document}.
7 schema:editor N3674c8e3c2f74ef5b3d72c470e61a6ae
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N1ae467a9fe1544d38d86694fef8c15a6
12 schema:keywords additional requirements
13 adjacent nodes
14 algorithm
15 cases
16 embedding
17 first-order terms
18 four
19 graph
20 graph G
21 height
22 horizontal line segments
23 infinite number
24 line segments
25 nodes
26 number
27 optimal height
28 planar embedding
29 planar graphs
30 plane graph
31 plane graph G
32 representation
33 requirements
34 segments
35 terms
36 time algorithm
37 visibility representation
38 schema:name Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights
39 schema:pagination 67-77
40 schema:productId N787286ad01fd477b9d53c8bb92426dd4
41 N9f3e020bd7a24cbf9eec03e0c87fef6a
42 schema:publisher Nc5d7ccb459984e91bd97e35ade55d4b3
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047130880
44 https://doi.org/10.1007/978-3-642-00219-9_8
45 schema:sdDatePublished 2022-05-10T10:50
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N90fdac26e6fd4f9aac0e9cbe0df774c6
48 schema:url https://doi.org/10.1007/978-3-642-00219-9_8
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N1ae467a9fe1544d38d86694fef8c15a6 schema:isbn 978-3-642-00218-2
53 978-3-642-00219-9
54 schema:name Graph Drawing
55 rdf:type schema:Book
56 N3674c8e3c2f74ef5b3d72c470e61a6ae rdf:first Neabc59bf23844573a7d0db71f9612f34
57 rdf:rest Ncdc4bd3915464a058dcf7bc892cea0dd
58 N4797efab703041d587fe3840ec054f57 rdf:first sg:person.012550135175.78
59 rdf:rest Nbd10002658d94225aaca7f07c7bacdfd
60 N5c313d471c9e423fba41a56d427d0f88 schema:familyName Patrignani
61 schema:givenName Maurizio
62 rdf:type schema:Person
63 N641719bdb52349b1a70dfdf64ada6bc7 rdf:first sg:person.011752554575.49
64 rdf:rest N4797efab703041d587fe3840ec054f57
65 N787286ad01fd477b9d53c8bb92426dd4 schema:name dimensions_id
66 schema:value pub.1047130880
67 rdf:type schema:PropertyValue
68 N90fdac26e6fd4f9aac0e9cbe0df774c6 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 N9f3e020bd7a24cbf9eec03e0c87fef6a schema:name doi
71 schema:value 10.1007/978-3-642-00219-9_8
72 rdf:type schema:PropertyValue
73 Nbd10002658d94225aaca7f07c7bacdfd rdf:first sg:person.013345515575.46
74 rdf:rest rdf:nil
75 Nc5d7ccb459984e91bd97e35ade55d4b3 schema:name Springer Nature
76 rdf:type schema:Organisation
77 Ncdc4bd3915464a058dcf7bc892cea0dd rdf:first N5c313d471c9e423fba41a56d427d0f88
78 rdf:rest rdf:nil
79 Neabc59bf23844573a7d0db71f9612f34 schema:familyName Tollis
80 schema:givenName Ioannis G.
81 rdf:type schema:Person
82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
83 schema:name Mathematical Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
86 schema:name Pure Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.011752554575.49 schema:affiliation grid-institutes:grid.19188.39
89 schema:familyName Chen
90 schema:givenName Chieh-Yu
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011752554575.49
92 rdf:type schema:Person
93 sg:person.012550135175.78 schema:affiliation grid-institutes:grid.19188.39
94 schema:familyName Hung
95 schema:givenName Ya-Fei
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012550135175.78
97 rdf:type schema:Person
98 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
99 schema:familyName Lu
100 schema:givenName Hsueh-I
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
102 rdf:type schema:Person
103 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University, Taiwan
104 Graduate Institute of Networking and Multimedia, National Taiwan University, 1 Roosevelt Road, Section 4, Taipei 106, Taiwan, ROC
105 schema:name Department of Computer Science and Information Engineering, National Taiwan University, Taiwan
106 Graduate Institute of Networking and Multimedia, National Taiwan University, 1 Roosevelt Road, Section 4, Taipei 106, Taiwan, ROC
107 rdf:type schema:Organization
 




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


...