Two algorithms for finding rectangular duals of planar graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1994

AUTHORS

Goos Kant , Xin He

ABSTRACT

We present two linear-time algorithms for computing a regular edge labeling of 4-connected planar triangular graphs. This labeling is used to compute in linear time a rectangular dual of this class of planar graphs. The two algorithms are based on totally different frameworks, and both are conceptually simpler than the previous known algorithm and are of independent interests. The first algorithm is based on edge contraction. The second algorithm is based on the canonical ordering. This ordering can also be used to compute more compact visibility representations for this class of planar graphs. More... »

PAGES

396-410

References to SciGraph publications

Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-540-57899-4
978-3-540-48385-4

From Grant

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57899-4_69

DOI

http://dx.doi.org/10.1007/3-540-57899-4_69

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Utrecht University", 
          "id": "https://www.grid.ac/institutes/grid.5477.1", 
          "name": [
            "Department of Computer Science, Utrecht University, Padualaan 14, 3584\u00a0CH Utrecht, the Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kant", 
        "givenName": "Goos", 
        "id": "sg:person.013743554756.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University at Buffalo, State University of New York", 
          "id": "https://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, State University of New York at Buffalo, 14260\u00a0Buffalo, 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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01762117", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003139574", 
          "https://doi.org/10.1007/bf01762117"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762117", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003139574", 
          "https://doi.org/10.1007/bf01762117"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008881195", 
          "https://doi.org/10.1007/bf02187706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008881195", 
          "https://doi.org/10.1007/bf02187706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008881195", 
          "https://doi.org/10.1007/bf02187706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187705", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027312329", 
          "https://doi.org/10.1007/bf02187705"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187705", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027312329", 
          "https://doi.org/10.1007/bf02187705"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230170306", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036072538"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0222072", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842475"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1992.267814", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086359610"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "We present two linear-time algorithms for computing a regular edge labeling of 4-connected planar triangular graphs. This labeling is used to compute in linear time a rectangular dual of this class of planar graphs. The two algorithms are based on totally different frameworks, and both are conceptually simpler than the previous known algorithm and are of independent interests. The first algorithm is based on edge contraction. The second algorithm is based on the canonical ordering. This ordering can also be used to compute more compact visibility representations for this class of planar graphs.", 
    "editor": [
      {
        "familyName": "Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57899-4_69", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3383643", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-57899-4", 
        "978-3-540-48385-4"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "name": "Two algorithms for finding rectangular duals of planar graphs", 
    "pagination": "396-410", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57899-4_69"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "5a1ad271284d6be45f40e572f433555f3a0fd07da54314b243edbb9cc319fb47"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018910920"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57899-4_69", 
      "https://app.dimensions.ai/details/publication/pub.1018910920"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T14:10", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000032.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-57899-4_69"
  }
]
 

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-57899-4_69'

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-57899-4_69'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57899-4_69'

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-57899-4_69'


 

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

98 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57899-4_69 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9fb56cc6cef34387afb16dcd8d99879b
4 schema:citation sg:pub.10.1007/bf01762117
5 sg:pub.10.1007/bf02187705
6 sg:pub.10.1007/bf02187706
7 https://doi.org/10.1002/net.3230170306
8 https://doi.org/10.1109/sfcs.1992.267814
9 https://doi.org/10.1137/0222072
10 schema:datePublished 1994
11 schema:datePublishedReg 1994-01-01
12 schema:description We present two linear-time algorithms for computing a regular edge labeling of 4-connected planar triangular graphs. This labeling is used to compute in linear time a rectangular dual of this class of planar graphs. The two algorithms are based on totally different frameworks, and both are conceptually simpler than the previous known algorithm and are of independent interests. The first algorithm is based on edge contraction. The second algorithm is based on the canonical ordering. This ordering can also be used to compute more compact visibility representations for this class of planar graphs.
13 schema:editor N7c6e47622d2d4b5f8a9a839690f89f11
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf N8202ec456685451b92d35dbde84121a3
18 schema:name Two algorithms for finding rectangular duals of planar graphs
19 schema:pagination 396-410
20 schema:productId N49fde0b02c0e40538101ef487ab15840
21 N5499aca14e6b4f24ae26868a035f227a
22 Nf683c5986c7046da83604425a57057d6
23 schema:publisher N28f4a7b7848349f185b6095e951a37d6
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018910920
25 https://doi.org/10.1007/3-540-57899-4_69
26 schema:sdDatePublished 2019-04-15T14:10
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N4c5a344236dc46e6899af58bd135f970
29 schema:url http://link.springer.com/10.1007/3-540-57899-4_69
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N28f4a7b7848349f185b6095e951a37d6 schema:location Berlin, Heidelberg
34 schema:name Springer Berlin Heidelberg
35 rdf:type schema:Organisation
36 N49fde0b02c0e40538101ef487ab15840 schema:name doi
37 schema:value 10.1007/3-540-57899-4_69
38 rdf:type schema:PropertyValue
39 N4c5a344236dc46e6899af58bd135f970 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N5499aca14e6b4f24ae26868a035f227a schema:name dimensions_id
42 schema:value pub.1018910920
43 rdf:type schema:PropertyValue
44 N6ca736a1386e41f4bbba36ae98e213ef rdf:first sg:person.011352641523.42
45 rdf:rest rdf:nil
46 N7c6e47622d2d4b5f8a9a839690f89f11 rdf:first Ncf5c69316fbc44b296c05ac23c284b4e
47 rdf:rest rdf:nil
48 N8202ec456685451b92d35dbde84121a3 schema:isbn 978-3-540-48385-4
49 978-3-540-57899-4
50 schema:name Graph-Theoretic Concepts in Computer Science
51 rdf:type schema:Book
52 N9fb56cc6cef34387afb16dcd8d99879b rdf:first sg:person.013743554756.94
53 rdf:rest N6ca736a1386e41f4bbba36ae98e213ef
54 Ncf5c69316fbc44b296c05ac23c284b4e schema:familyName Leeuwen
55 schema:givenName Jan
56 rdf:type schema:Person
57 Nf683c5986c7046da83604425a57057d6 schema:name readcube_id
58 schema:value 5a1ad271284d6be45f40e572f433555f3a0fd07da54314b243edbb9cc319fb47
59 rdf:type schema:PropertyValue
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
64 schema:name Computation Theory and Mathematics
65 rdf:type schema:DefinedTerm
66 sg:grant.3383643 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-57899-4_69
67 rdf:type schema:MonetaryGrant
68 sg:person.011352641523.42 schema:affiliation https://www.grid.ac/institutes/grid.273335.3
69 schema:familyName He
70 schema:givenName Xin
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
72 rdf:type schema:Person
73 sg:person.013743554756.94 schema:affiliation https://www.grid.ac/institutes/grid.5477.1
74 schema:familyName Kant
75 schema:givenName Goos
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94
77 rdf:type schema:Person
78 sg:pub.10.1007/bf01762117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003139574
79 https://doi.org/10.1007/bf01762117
80 rdf:type schema:CreativeWork
81 sg:pub.10.1007/bf02187705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
82 https://doi.org/10.1007/bf02187705
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
85 https://doi.org/10.1007/bf02187706
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1002/net.3230170306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036072538
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1109/sfcs.1992.267814 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086359610
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1137/0222072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842475
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.273335.3 schema:alternateName University at Buffalo, State University of New York
94 schema:name Department of Computer Science, State University of New York at Buffalo, 14260 Buffalo, NY, USA
95 rdf:type schema:Organization
96 https://www.grid.ac/institutes/grid.5477.1 schema:alternateName Utrecht University
97 schema:name Department of Computer Science, Utrecht University, Padualaan 14, 3584 CH Utrecht, the Netherlands
98 rdf:type schema:Organization
 




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


...