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": "2022-01-01T18:14", 
    "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/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 N9abd552bd49345b981f00c1bb336f153
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 Na75de66975774bb1b2ea048fbed955c2
11 Nb1d2959723214ca7a604818044e001de
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 N25aff5966c964f14ac03370fad3ab820
53 N7b6c34c8ac784141a94fb20695b7bf88
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021220162
55 https://doi.org/10.1007/s00454-004-1154-y
56 schema:sdDatePublished 2022-01-01T18:14
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N91e53351f78443389cc05ba5f534bfad
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 N25aff5966c964f14ac03370fad3ab820 schema:name doi
64 schema:value 10.1007/s00454-004-1154-y
65 rdf:type schema:PropertyValue
66 N7b6c34c8ac784141a94fb20695b7bf88 schema:name dimensions_id
67 schema:value pub.1021220162
68 rdf:type schema:PropertyValue
69 N7c7f481e85af43008855121a2a1cbc8e rdf:first sg:person.011352641523.42
70 rdf:rest rdf:nil
71 N91e53351f78443389cc05ba5f534bfad schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N9abd552bd49345b981f00c1bb336f153 rdf:first sg:person.012041227127.88
74 rdf:rest N7c7f481e85af43008855121a2a1cbc8e
75 Na75de66975774bb1b2ea048fbed955c2 schema:volumeNumber 33
76 rdf:type schema:PublicationVolume
77 Nb1d2959723214ca7a604818044e001de schema:issueNumber 2
78 rdf:type schema:PublicationIssue
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)


...