Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

AUTHORS

Huaming Zhang , Xin He

ABSTRACT

We study the properties of Schnyder’s realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a visibility representation 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}$\lceil \frac{15n}{16} \rceil$\end{document}. This improves the previous best bound of n-1. The drawing can be obtained in linear time. Second, we show that every plane graph G has a straight-line grid embedding on an (n − Δ0 − 1) × (n − Δ0 − 1) grid, where Δ0 is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n-1) × (n-1). This embedding can also be found in O(n) time. More... »

PAGES

493-504

Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-40545-0
978-3-540-45078-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-45078-8_43

DOI

http://dx.doi.org/10.1007/978-3-540-45078-8_43

DIMENSIONS

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


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 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": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "We study the properties of Schnyder\u2019s realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a visibility representation 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}$\\lceil \\frac{15n}{16} \\rceil$\\end{document}. This improves the previous best bound of n-1. The drawing can be obtained in linear time. Second, we show that every plane graph G has a straight-line grid embedding on an (n\u2009\u2212\u2009\u03940\u2009\u2212\u20091) \u00d7 (n\u2009\u2212\u2009\u03940\u2009\u2212\u20091) grid, where \u03940 is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n-1) \u00d7 (n-1). This embedding can also be found in O(n) time.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Smid", 
        "givenName": "Michiel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-45078-8_43", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40545-0", 
        "978-3-540-45078-8"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "Schnyder\u2019s realizers", 
      "graph", 
      "compact drawings", 
      "graph G", 
      "linear time", 
      "grid", 
      "cyclic faces", 
      "embedding", 
      "Compact Visibility Representation", 
      "grid embedding", 
      "properties", 
      "realizers", 
      "trees", 
      "plane graph", 
      "drawings", 
      "style", 
      "plane graph G", 
      "vertices", 
      "visibility representation", 
      "representation", 
      "N-1", 
      "time", 
      "straight-line grid", 
      "\u03940", 
      "number", 
      "face", 
      "respect", 
      "height", 
      "canonical ordering tree", 
      "ordering trees", 
      "minimum realizer", 
      "Straight-Line Grid Embedding"
    ], 
    "name": "Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs", 
    "pagination": "493-504", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007042305"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-45078-8_43"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-45078-8_43", 
      "https://app.dimensions.ai/details/publication/pub.1007042305"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:58", 
    "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_38.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-45078-8_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-45078-8_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-45078-8_43'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45078-8_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-45078-8_43'


 

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

109 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-45078-8_43 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N7adb3603ab1b4a0999e24d814da23723
4 schema:datePublished 2003
5 schema:datePublishedReg 2003-01-01
6 schema:description We study the properties of Schnyder’s realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a visibility representation 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}$\lceil \frac{15n}{16} \rceil$\end{document}. This improves the previous best bound of n-1. The drawing can be obtained in linear time. Second, we show that every plane graph G has a straight-line grid embedding on an (n − Δ0 − 1) × (n − Δ0 − 1) grid, where Δ0 is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n-1) × (n-1). This embedding can also be found in O(n) time.
7 schema:editor N13569a667ad947daa1d9d83c37b765b3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N30cea5b063d046d69ccbaa3a2d0bdd74
12 schema:keywords Compact Visibility Representation
13 N-1
14 Schnyder’s realizers
15 Straight-Line Grid Embedding
16 canonical ordering tree
17 compact drawings
18 cyclic faces
19 drawings
20 embedding
21 face
22 graph
23 graph G
24 grid
25 grid embedding
26 height
27 linear time
28 minimum realizer
29 number
30 ordering trees
31 plane graph
32 plane graph G
33 properties
34 realizers
35 representation
36 respect
37 straight-line grid
38 style
39 time
40 trees
41 vertices
42 visibility representation
43 Δ0
44 schema:name Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs
45 schema:pagination 493-504
46 schema:productId N3daad8b5700347acb5fe38b1723b3736
47 N3f3f70b02a70469790b1950b060c8e23
48 schema:publisher Nfb3fecf3c0884bfb83ec039ab36803b0
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007042305
50 https://doi.org/10.1007/978-3-540-45078-8_43
51 schema:sdDatePublished 2021-11-01T18:58
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N743119c391444abc831f5e9fe43cae2c
54 schema:url https://doi.org/10.1007/978-3-540-45078-8_43
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N0821e9d58fec4af0bb71af2f91ddb5bb schema:familyName Dehne
59 schema:givenName Frank
60 rdf:type schema:Person
61 N11b79f8bffb1403297d99a79432b4f27 rdf:first Nf525fa0fba364d29a10d215baa42a325
62 rdf:rest Nf458da346a7c42088310d927166fa522
63 N13569a667ad947daa1d9d83c37b765b3 rdf:first N0821e9d58fec4af0bb71af2f91ddb5bb
64 rdf:rest N11b79f8bffb1403297d99a79432b4f27
65 N30cea5b063d046d69ccbaa3a2d0bdd74 schema:isbn 978-3-540-40545-0
66 978-3-540-45078-8
67 schema:name Algorithms and Data Structures
68 rdf:type schema:Book
69 N3daad8b5700347acb5fe38b1723b3736 schema:name doi
70 schema:value 10.1007/978-3-540-45078-8_43
71 rdf:type schema:PropertyValue
72 N3f3f70b02a70469790b1950b060c8e23 schema:name dimensions_id
73 schema:value pub.1007042305
74 rdf:type schema:PropertyValue
75 N743119c391444abc831f5e9fe43cae2c schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N7adb3603ab1b4a0999e24d814da23723 rdf:first sg:person.012041227127.88
78 rdf:rest Ndd4771dd1bdd410a9a5969a2397e9816
79 Nb056dd74047c4ba69ce2492ece1ad301 schema:familyName Smid
80 schema:givenName Michiel
81 rdf:type schema:Person
82 Ndd4771dd1bdd410a9a5969a2397e9816 rdf:first sg:person.011352641523.42
83 rdf:rest rdf:nil
84 Nf458da346a7c42088310d927166fa522 rdf:first Nb056dd74047c4ba69ce2492ece1ad301
85 rdf:rest rdf:nil
86 Nf525fa0fba364d29a10d215baa42a325 schema:familyName Sack
87 schema:givenName Jörg-Rüdiger
88 rdf:type schema:Person
89 Nfb3fecf3c0884bfb83ec039ab36803b0 schema:name Springer Nature
90 rdf:type schema:Organisation
91 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
92 schema:name Mathematical Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
95 schema:name Pure Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
98 schema:familyName He
99 schema:givenName Xin
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
101 rdf:type schema:Person
102 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.273335.3
103 schema:familyName Zhang
104 schema:givenName Huaming
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
106 rdf:type schema:Person
107 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
108 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
109 rdf:type schema:Organization
 




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


...