Canonical Ordering Trees and Their Applications in Graph Drawing View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2005-01-14

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 ⌈ 15n/16 ⌉. This improves the previous best bound of (n - 1). 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). We also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these properties, we show that every such a graph has a canonical ordering tree with at most ⌈ (n + 1)/2 ⌉ leaves. This improves the previously known bound of ⌊ (2n + 1)/3 ⌋. We show that every 4-connected plane graph has a visibility representation with height at most ⌈ 3n/4 ⌉. All drawings discussed in this paper can be obtained in linear time. More... »

PAGES

321-344

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00454-004-1154-y

DOI

http://dx.doi.org/10.1007/s00454-004-1154-y

DIMENSIONS

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


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, State University of New York at Buffalo, Buffalo, NY 14260, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, 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, State University of New York at Buffalo, Buffalo, NY 14260, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, 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-01-14", 
    "datePublishedReg": "2005-01-14", 
    "description": "Abstract\nWe study the properties of Schnyder\u2019s realizers and canonical ordering trees of plane graphs. Based on these newly \ndiscovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First, we show that G has a\nvisibility representation with height at most \u2308 15n/16 \u2309. This improves the previous best bound\nof (n - 1). Second, we show that every plane graph G has a straight-line grid\nembedding on an (n - \u03b40 - 1) \u00d7 (n - \u03b40 - 1) grid, where \u03b40 is the number of cyclic faces of G with respect to its\nminimum realizer. This improves the previous best bound of (n - 1) \u00d7 (n - 1). \nWe also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these\nproperties, we show that every such a graph has a canonical ordering tree with at most \u2308 (n + 1)/2 \u2309 leaves.\nThis improves the previously known bound of \u230a (2n + 1)/3 \u230b.  \nWe show that every 4-connected plane graph has a visibility\nrepresentation with height at most \u2308 3n/4 \u2309.\nAll drawings discussed in this paper can be obtained in linear time.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00454-004-1154-y", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1043660", 
        "issn": [
          "0179-5376", 
          "1432-0444"
        ], 
        "name": "Discrete & Computational Geometry", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "33"
      }
    ], 
    "keywords": [
      "Schnyder\u2019s realizers", 
      "graph", 
      "linear time", 
      "graph drawing", 
      "realizers", 
      "trees", 
      "plane graph", 
      "compact drawings", 
      "drawings", 
      "plane graph G", 
      "graph G", 
      "representation", 
      "straight-line grid", 
      "grid", 
      "regular edge labeling", 
      "edge labeling", 
      "style", 
      "vertices", 
      "visibility representation", 
      "number", 
      "face", 
      "plane triangulations", 
      "triangulation", 
      "visibility", 
      "time", 
      "applications", 
      "properties", 
      "respect", 
      "labeling", 
      "height", 
      "cyclic faces", 
      "leaves", 
      "canonical ordering tree", 
      "ordering trees", 
      "\u03940", 
      "minimum realizer", 
      "paper"
    ], 
    "name": "Canonical Ordering Trees and Their Applications in Graph Drawing", 
    "pagination": "321-344", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021220162"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00454-004-1154-y"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00454-004-1154-y", 
      "https://app.dimensions.ai/details/publication/pub.1021220162"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_404.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00454-004-1154-y"
  }
]
 

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/s00454-004-1154-y'

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/s00454-004-1154-y'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00454-004-1154-y'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00454-004-1154-y'


 

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

102 TRIPLES      21 PREDICATES      62 URIs      54 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00454-004-1154-y schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nae84ce4fe8d84523893d55413326dde2
4 schema:datePublished 2005-01-14
5 schema:datePublishedReg 2005-01-14
6 schema:description 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 ⌈ 15n/16 ⌉. This improves the previous best bound of (n - 1). 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). We also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these properties, we show that every such a graph has a canonical ordering tree with at most ⌈ (n + 1)/2 ⌉ leaves. This improves the previously known bound of ⌊ (2n + 1)/3 ⌋. We show that every 4-connected plane graph has a visibility representation with height at most ⌈ 3n/4 ⌉. All drawings discussed in this paper can be obtained in linear time.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N3cf98c0c11394090872f93a282343a60
11 N674d2f71c1ce47838870db07fb450e84
12 sg:journal.1043660
13 schema:keywords Schnyder’s realizers
14 applications
15 canonical ordering tree
16 compact drawings
17 cyclic faces
18 drawings
19 edge labeling
20 face
21 graph
22 graph G
23 graph drawing
24 grid
25 height
26 labeling
27 leaves
28 linear time
29 minimum realizer
30 number
31 ordering trees
32 paper
33 plane graph
34 plane graph G
35 plane triangulations
36 properties
37 realizers
38 regular edge labeling
39 representation
40 respect
41 straight-line grid
42 style
43 time
44 trees
45 triangulation
46 vertices
47 visibility
48 visibility representation
49 Δ0
50 schema:name Canonical Ordering Trees and Their Applications in Graph Drawing
51 schema:pagination 321-344
52 schema:productId N2e05a27f10974a6295a0181809f182d7
53 Ned733ef40b9545fe88308d6fa93e1317
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021220162
55 https://doi.org/10.1007/s00454-004-1154-y
56 schema:sdDatePublished 2021-12-01T19:17
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher Naa44b142e41b4664928ef9ce7401044f
59 schema:url https://doi.org/10.1007/s00454-004-1154-y
60 sgo:license sg:explorer/license/
61 sgo:sdDataset articles
62 rdf:type schema:ScholarlyArticle
63 N0037da2077494731bc2fdd3310e29cc5 rdf:first sg:person.011352641523.42
64 rdf:rest rdf:nil
65 N2e05a27f10974a6295a0181809f182d7 schema:name dimensions_id
66 schema:value pub.1021220162
67 rdf:type schema:PropertyValue
68 N3cf98c0c11394090872f93a282343a60 schema:volumeNumber 33
69 rdf:type schema:PublicationVolume
70 N674d2f71c1ce47838870db07fb450e84 schema:issueNumber 2
71 rdf:type schema:PublicationIssue
72 Naa44b142e41b4664928ef9ce7401044f schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Nae84ce4fe8d84523893d55413326dde2 rdf:first sg:person.012041227127.88
75 rdf:rest N0037da2077494731bc2fdd3310e29cc5
76 Ned733ef40b9545fe88308d6fa93e1317 schema:name doi
77 schema:value 10.1007/s00454-004-1154-y
78 rdf:type schema:PropertyValue
79 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
80 schema:name Mathematical Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
83 schema:name Pure Mathematics
84 rdf:type schema:DefinedTerm
85 sg:journal.1043660 schema:issn 0179-5376
86 1432-0444
87 schema:name Discrete & Computational Geometry
88 schema:publisher Springer Nature
89 rdf:type schema:Periodical
90 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
91 schema:familyName He
92 schema:givenName Xin
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
94 rdf:type schema:Person
95 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.273335.3
96 schema:familyName Zhang
97 schema:givenName Huaming
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
99 rdf:type schema:Person
100 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA
101 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA
102 rdf:type schema:Organization
 




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


...