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": "2022-01-01T19:12", 
    "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_21.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 N1f7a36f23a514da49ffbf1be415c774d
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 N657ab80242504defba379017881345a2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0d12b285ce0c48a9ac0951aaea1ecad0
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 N2624217031614e96866629a30bae2ee8
47 Nb0f81b3ecd504ff2b0f2f4edf1377058
48 schema:publisher N09b7d9ceac0a437bbf01eb4daf2830eb
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 2022-01-01T19:12
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Nbb93f91f9cb64dacbdaecf9c8da40670
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 N09b7d9ceac0a437bbf01eb4daf2830eb schema:name Springer Nature
59 rdf:type schema:Organisation
60 N0d12b285ce0c48a9ac0951aaea1ecad0 schema:isbn 978-3-540-40545-0
61 978-3-540-45078-8
62 schema:name Algorithms and Data Structures
63 rdf:type schema:Book
64 N1f7a36f23a514da49ffbf1be415c774d rdf:first sg:person.012041227127.88
65 rdf:rest N68906e2a2dfb4479ad405a48dbdddb93
66 N2624217031614e96866629a30bae2ee8 schema:name dimensions_id
67 schema:value pub.1007042305
68 rdf:type schema:PropertyValue
69 N284302490fca43b6a0e458f696e35add rdf:first N629ea857cc284e9c972f297480d59058
70 rdf:rest N3eb24fdf62ad4cb4862f0247599e2a06
71 N3eb24fdf62ad4cb4862f0247599e2a06 rdf:first N9b81409db30f4f62b897eabc0a7ae72a
72 rdf:rest rdf:nil
73 N629ea857cc284e9c972f297480d59058 schema:familyName Sack
74 schema:givenName Jörg-Rüdiger
75 rdf:type schema:Person
76 N657ab80242504defba379017881345a2 rdf:first Nf209cbe0dde24ac296925898a60db0f1
77 rdf:rest N284302490fca43b6a0e458f696e35add
78 N68906e2a2dfb4479ad405a48dbdddb93 rdf:first sg:person.011352641523.42
79 rdf:rest rdf:nil
80 N9b81409db30f4f62b897eabc0a7ae72a schema:familyName Smid
81 schema:givenName Michiel
82 rdf:type schema:Person
83 Nb0f81b3ecd504ff2b0f2f4edf1377058 schema:name doi
84 schema:value 10.1007/978-3-540-45078-8_43
85 rdf:type schema:PropertyValue
86 Nbb93f91f9cb64dacbdaecf9c8da40670 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nf209cbe0dde24ac296925898a60db0f1 schema:familyName Dehne
89 schema:givenName Frank
90 rdf:type schema:Person
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)


...