Some Applications of Orderly Spanning Trees in Graph Drawing View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-11-08

AUTHORS

Ho-Lin Chen , Chien-Chih Liao , Hsueh-I Lu , Hsu-Chun Yen

ABSTRACT

Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this paper provides new evidence to demonstrate such a potential. Two applications of the orderly spanning trees of plane graphs are investigated. Our first application deals with Podevs drawing, i.e., planar orthogonal drawing with equal vertex size, introduced by Fößmeier and Kaufmann. Based upon orderly spanning trees, we give an algorithm that produces a Podevs drawing with half-perimeter no more than [3n/2] + 1 and at most one bend per edge for any n-node plane graph with maximal degree Δ, a notable improvement over the existing results in the literature in terms of the size of the drawing area. The second application is an alternative proof for the sufficient and necessary condition for a graph to admit a rectangular dual, i.e., a floor-plan using only rectangles. More... »

PAGES

332-343

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-36151-0_31

DOI

http://dx.doi.org/10.1007/3-540-36151-0_31

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Ho-Lin", 
        "id": "sg:person.012704570265.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012704570265.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liao", 
        "givenName": "Chien-Chih", 
        "id": "sg:person.014703620455.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014703620455.71"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.506928.0", 
          "name": [
            "Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, Republic of China"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yen", 
        "givenName": "Hsu-Chun", 
        "id": "sg:person.015077575457.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015077575457.09"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-11-08", 
    "datePublishedReg": "2002-11-08", 
    "description": "Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this paper provides new evidence to demonstrate such a potential. Two applications of the orderly spanning trees of plane graphs are investigated. Our first application deals with Podevs drawing, i.e., planar orthogonal drawing with equal vertex size, introduced by F\u00f6\u00dfmeier and Kaufmann. Based upon orderly spanning trees, we give an algorithm that produces a Podevs drawing with half-perimeter no more than [3n/2] + 1 and at most one bend per edge for any n-node plane graph with maximal degree \u0394, a notable improvement over the existing results in the literature in terms of the size of the drawing area. The second application is an alternative proof for the sufficient and necessary condition for a graph to admit a rectangular dual, i.e., a floor-plan using only rectangles.", 
    "editor": [
      {
        "familyName": "Goodrich", 
        "givenName": "Michael T.", 
        "type": "Person"
      }, 
      {
        "familyName": "Kobourov", 
        "givenName": "Stephen G.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-36151-0_31", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-00158-4", 
        "978-3-540-36151-0"
      ], 
      "name": "Graph Drawing", 
      "type": "Book"
    }, 
    "keywords": [
      "graph drawing", 
      "spanning tree", 
      "plane graph", 
      "orderly spanning trees", 
      "maximal degree \u0394", 
      "degree \u0394", 
      "only rectangles", 
      "new results", 
      "vertex size", 
      "alternative proof", 
      "necessary condition", 
      "graph", 
      "second application", 
      "application deals", 
      "first application deals", 
      "applications", 
      "drawing area", 
      "algorithm", 
      "rectangle", 
      "proof", 
      "promising technique", 
      "planar", 
      "edge", 
      "results", 
      "terms", 
      "notable improvement", 
      "trees", 
      "technique", 
      "size", 
      "Kaufmann", 
      "bend", 
      "conditions", 
      "potential", 
      "drawings", 
      "deal", 
      "literature", 
      "exploration", 
      "improvement", 
      "area", 
      "paper", 
      "evidence", 
      "new evidence"
    ], 
    "name": "Some Applications of Orderly Spanning Trees in Graph Drawing", 
    "pagination": "332-343", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014210834"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-36151-0_31"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-36151-0_31", 
      "https://app.dimensions.ai/details/publication/pub.1014210834"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:41", 
    "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_203.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-36151-0_31"
  }
]
 

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/3-540-36151-0_31'

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/3-540-36151-0_31'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36151-0_31'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-36151-0_31'


 

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

131 TRIPLES      23 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-36151-0_31 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N30abdbf489a44822b069a75b52bacfcc
4 schema:datePublished 2002-11-08
5 schema:datePublishedReg 2002-11-08
6 schema:description Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this paper provides new evidence to demonstrate such a potential. Two applications of the orderly spanning trees of plane graphs are investigated. Our first application deals with Podevs drawing, i.e., planar orthogonal drawing with equal vertex size, introduced by Fößmeier and Kaufmann. Based upon orderly spanning trees, we give an algorithm that produces a Podevs drawing with half-perimeter no more than [3n/2] + 1 and at most one bend per edge for any n-node plane graph with maximal degree Δ, a notable improvement over the existing results in the literature in terms of the size of the drawing area. The second application is an alternative proof for the sufficient and necessary condition for a graph to admit a rectangular dual, i.e., a floor-plan using only rectangles.
7 schema:editor N449b4f23538e430f9a3dc947e441454b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8382f07aa58c440998c644272249f85f
12 schema:keywords Kaufmann
13 algorithm
14 alternative proof
15 application deals
16 applications
17 area
18 bend
19 conditions
20 deal
21 degree Δ
22 drawing area
23 drawings
24 edge
25 evidence
26 exploration
27 first application deals
28 graph
29 graph drawing
30 improvement
31 literature
32 maximal degree Δ
33 necessary condition
34 new evidence
35 new results
36 notable improvement
37 only rectangles
38 orderly spanning trees
39 paper
40 planar
41 plane graph
42 potential
43 promising technique
44 proof
45 rectangle
46 results
47 second application
48 size
49 spanning tree
50 technique
51 terms
52 trees
53 vertex size
54 schema:name Some Applications of Orderly Spanning Trees in Graph Drawing
55 schema:pagination 332-343
56 schema:productId N1ff440c8744d429ebe449ef3484ebd86
57 N3330d042148047e9accb648020e69a80
58 schema:publisher Nfb08706432754fb39cc4f9852828de19
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014210834
60 https://doi.org/10.1007/3-540-36151-0_31
61 schema:sdDatePublished 2022-05-10T10:41
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher Nf9b14ba8ace04a7f89fcd7374b131d9b
64 schema:url https://doi.org/10.1007/3-540-36151-0_31
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N0e3c48d9487341c9b982b55b0b1adf9c rdf:first sg:person.015077575457.09
69 rdf:rest rdf:nil
70 N1ff440c8744d429ebe449ef3484ebd86 schema:name dimensions_id
71 schema:value pub.1014210834
72 rdf:type schema:PropertyValue
73 N30abdbf489a44822b069a75b52bacfcc rdf:first sg:person.012704570265.60
74 rdf:rest Nc7c3e22770554a7abf94bafaee611dfb
75 N3330d042148047e9accb648020e69a80 schema:name doi
76 schema:value 10.1007/3-540-36151-0_31
77 rdf:type schema:PropertyValue
78 N3efda61f226e42cf82c9fd2adae56148 rdf:first sg:person.013345515575.46
79 rdf:rest N0e3c48d9487341c9b982b55b0b1adf9c
80 N449b4f23538e430f9a3dc947e441454b rdf:first Ne42c983c392f4cb1be6576b900b8bf2a
81 rdf:rest Nab59c96297aa401283a8e1ba466a9773
82 N8382f07aa58c440998c644272249f85f schema:isbn 978-3-540-00158-4
83 978-3-540-36151-0
84 schema:name Graph Drawing
85 rdf:type schema:Book
86 Nab59c96297aa401283a8e1ba466a9773 rdf:first Nb389b57edbb94f8b8364cdb675fefe86
87 rdf:rest rdf:nil
88 Nb389b57edbb94f8b8364cdb675fefe86 schema:familyName Kobourov
89 schema:givenName Stephen G.
90 rdf:type schema:Person
91 Nc7c3e22770554a7abf94bafaee611dfb rdf:first sg:person.014703620455.71
92 rdf:rest N3efda61f226e42cf82c9fd2adae56148
93 Ne42c983c392f4cb1be6576b900b8bf2a schema:familyName Goodrich
94 schema:givenName Michael T.
95 rdf:type schema:Person
96 Nf9b14ba8ace04a7f89fcd7374b131d9b schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 Nfb08706432754fb39cc4f9852828de19 schema:name Springer Nature
99 rdf:type schema:Organisation
100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information and Computing Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
104 schema:name Computation Theory and Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.012704570265.60 schema:affiliation grid-institutes:grid.19188.39
107 schema:familyName Chen
108 schema:givenName Ho-Lin
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012704570265.60
110 rdf:type schema:Person
111 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.506928.0
112 schema:familyName Lu
113 schema:givenName Hsueh-I
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
115 rdf:type schema:Person
116 sg:person.014703620455.71 schema:affiliation grid-institutes:grid.19188.39
117 schema:familyName Liao
118 schema:givenName Chien-Chih
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014703620455.71
120 rdf:type schema:Person
121 sg:person.015077575457.09 schema:affiliation grid-institutes:grid.19188.39
122 schema:familyName Yen
123 schema:givenName Hsu-Chun
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015077575457.09
125 rdf:type schema:Person
126 grid-institutes:grid.19188.39 schema:alternateName Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China
127 schema:name Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China
128 rdf:type schema:Organization
129 grid-institutes:grid.506928.0 schema:alternateName Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, Republic of China
130 schema:name Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, Republic of China
131 rdf:type schema:Organization
 




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


...