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

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/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 Computer Science, Utrecht University, Padualaan 14, 3584, CH Utrecht, the Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.5477.1", 
          "name": [
            "Department of Computer Science, Utrecht University, Padualaan 14, 3584, CH 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": "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, State University of New York 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": "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, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57899-4", 
        "978-3-540-48385-4"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "linear-time algorithm", 
      "planar graphs", 
      "rectangular duals", 
      "second algorithm", 
      "first algorithm", 
      "algorithm", 
      "linear time", 
      "graph", 
      "independent interest", 
      "canonical ordering", 
      "edge contraction", 
      "regular edge labeling", 
      "different frameworks", 
      "Compact Visibility Representation", 
      "edge labeling", 
      "framework", 
      "representation", 
      "class", 
      "visibility representation", 
      "ordering", 
      "interest", 
      "time", 
      "labeling", 
      "triangular graph", 
      "dual", 
      "contraction", 
      "planar triangular graphs", 
      "more compact visibility representations"
    ], 
    "name": "Two algorithms for finding rectangular duals of planar graphs", 
    "pagination": "396-410", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018910920"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57899-4_69"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57899-4_69", 
      "https://app.dimensions.ai/details/publication/pub.1018910920"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_84.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/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      54 URIs      47 LITERALS      7 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 Ne9d8d8ae41cb44228f8eb1a020b473d8
4 schema:datePublished 1994
5 schema:datePublishedReg 1994-01-01
6 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.
7 schema:editor N2c9b441bc7b143ce9824c82250c26f01
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7ab7d1aaac204aa39a78850575a0237e
12 schema:keywords Compact Visibility Representation
13 algorithm
14 canonical ordering
15 class
16 contraction
17 different frameworks
18 dual
19 edge contraction
20 edge labeling
21 first algorithm
22 framework
23 graph
24 independent interest
25 interest
26 labeling
27 linear time
28 linear-time algorithm
29 more compact visibility representations
30 ordering
31 planar graphs
32 planar triangular graphs
33 rectangular duals
34 regular edge labeling
35 representation
36 second algorithm
37 time
38 triangular graph
39 visibility representation
40 schema:name Two algorithms for finding rectangular duals of planar graphs
41 schema:pagination 396-410
42 schema:productId Nacfe26c2e4004e11815da0dbdcc5d09e
43 Nec800300da4a46e5b153b48ed43b2691
44 schema:publisher N740a54e342ae4a168deb114c5eb4a27a
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018910920
46 https://doi.org/10.1007/3-540-57899-4_69
47 schema:sdDatePublished 2021-11-01T19:04
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Nb40e3507b1c84065b9c648dba40d2a69
50 schema:url https://doi.org/10.1007/3-540-57899-4_69
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N1c32dbb248044b47840c22b925ca93e9 rdf:first sg:person.011352641523.42
55 rdf:rest rdf:nil
56 N2c9b441bc7b143ce9824c82250c26f01 rdf:first N897b10d6757b4ce18ad6ceebd4c825f8
57 rdf:rest rdf:nil
58 N740a54e342ae4a168deb114c5eb4a27a schema:name Springer Nature
59 rdf:type schema:Organisation
60 N7ab7d1aaac204aa39a78850575a0237e schema:isbn 978-3-540-48385-4
61 978-3-540-57899-4
62 schema:name Graph-Theoretic Concepts in Computer Science
63 rdf:type schema:Book
64 N897b10d6757b4ce18ad6ceebd4c825f8 schema:familyName Leeuwen
65 schema:givenName Jan
66 rdf:type schema:Person
67 Nacfe26c2e4004e11815da0dbdcc5d09e schema:name dimensions_id
68 schema:value pub.1018910920
69 rdf:type schema:PropertyValue
70 Nb40e3507b1c84065b9c648dba40d2a69 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 Ne9d8d8ae41cb44228f8eb1a020b473d8 rdf:first sg:person.013743554756.94
73 rdf:rest N1c32dbb248044b47840c22b925ca93e9
74 Nec800300da4a46e5b153b48ed43b2691 schema:name doi
75 schema:value 10.1007/3-540-57899-4_69
76 rdf:type schema:PropertyValue
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
81 schema:name Computation Theory and Mathematics
82 rdf:type schema:DefinedTerm
83 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
84 schema:familyName He
85 schema:givenName Xin
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
87 rdf:type schema:Person
88 sg:person.013743554756.94 schema:affiliation grid-institutes:grid.5477.1
89 schema:familyName Kant
90 schema:givenName Goos
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94
92 rdf:type schema:Person
93 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
94 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
95 rdf:type schema:Organization
96 grid-institutes:grid.5477.1 schema:alternateName Department of Computer Science, Utrecht University, Padualaan 14, 3584, CH Utrecht, the Netherlands
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)


...