A unified approach to visibility representations of planar graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1986-12

AUTHORS

Roberto Tamassia, Ioannis G. Tollis

ABSTRACT

We studyvisibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments that intersect only adjacent vertex-segments. Every graph that admits this representation must be planar. We consider three types of visibility representations, and we give complete characterizations of the classes of graphs that admit them. Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations of planar graphs. Many applications of our results can be found in VLSI layout. More... »

PAGES

321-341

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02187705

DOI

http://dx.doi.org/10.1007/bf02187705

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Illinois at Urbana Champaign", 
          "id": "https://www.grid.ac/institutes/grid.35403.31", 
          "name": [
            "Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, 61801, Urbana, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "id": "sg:person.0674326220.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Illinois at Urbana Champaign", 
          "id": "https://www.grid.ac/institutes/grid.35403.31", 
          "name": [
            "Coordinated Science Laboratory and Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tollis", 
        "givenName": "Ioannis G.", 
        "id": "sg:person.07523205527.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07523205527.24"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/323233.323253", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002612669"
        ], 
        "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": "https://doi.org/10.1090/s0002-9947-1956-0081471-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015583804"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321850.321852", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023277958"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230140202", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023775252"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(76)90086-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035496339"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(83)90128-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041600793"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0211042", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841658"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109703686", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-349-03521-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109703686", 
          "https://doi.org/10.1007/978-1-349-03521-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-349-03521-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109703686", 
          "https://doi.org/10.1007/978-1-349-03521-2"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1986-12", 
    "datePublishedReg": "1986-12-01", 
    "description": "We studyvisibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments that intersect only adjacent vertex-segments. Every graph that admits this representation must be planar. We consider three types of visibility representations, and we give complete characterizations of the classes of graphs that admit them. Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations of planar graphs. Many applications of our results can be found in VLSI layout.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02187705", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1043660", 
        "issn": [
          "0179-5376", 
          "1432-0444"
        ], 
        "name": "Discrete & Computational Geometry", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "name": "A unified approach to visibility representations of planar graphs", 
    "pagination": "321-341", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "821b49c9330d57d09d9c5e7eba7faa8548dedb63dd59d5d1e9309c0f6a1e7c4b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02187705"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027312329"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02187705", 
      "https://app.dimensions.ai/details/publication/pub.1027312329"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:11", 
    "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/0000000367_0000000367/records_88255_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2FBF02187705"
  }
]
 

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/bf02187705'

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/bf02187705'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02187705'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02187705'


 

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

100 TRIPLES      21 PREDICATES      37 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02187705 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ncae36c84a23c48109e514af987ccc880
4 schema:citation sg:pub.10.1007/978-1-349-03521-2
5 sg:pub.10.1007/bf02187706
6 https://app.dimensions.ai/details/publication/pub.1109703686
7 https://doi.org/10.1002/net.3230140202
8 https://doi.org/10.1016/0012-365x(83)90128-0
9 https://doi.org/10.1016/0304-3975(76)90086-4
10 https://doi.org/10.1090/s0002-9947-1956-0081471-8
11 https://doi.org/10.1137/0211042
12 https://doi.org/10.1145/321850.321852
13 https://doi.org/10.1145/323233.323253
14 schema:datePublished 1986-12
15 schema:datePublishedReg 1986-12-01
16 schema:description We studyvisibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments that intersect only adjacent vertex-segments. Every graph that admits this representation must be planar. We consider three types of visibility representations, and we give complete characterizations of the classes of graphs that admit them. Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations of planar graphs. Many applications of our results can be found in VLSI layout.
17 schema:genre research_article
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N54ca240fb91945409345e1f1c7cf6ec0
21 N7fe3c394514f482c92db36be2e1b24e2
22 sg:journal.1043660
23 schema:name A unified approach to visibility representations of planar graphs
24 schema:pagination 321-341
25 schema:productId N6809bd186a004c09b477e3e5da2f5f51
26 Nd85c5dbe403d4d2aacd6871d1c9400a6
27 Nf5f5b6a763db423c8a22506224b8c32f
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
29 https://doi.org/10.1007/bf02187705
30 schema:sdDatePublished 2019-04-11T13:11
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N03baab1db884458ab0d6ef85a4e7749a
33 schema:url https://link.springer.com/10.1007%2FBF02187705
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N03baab1db884458ab0d6ef85a4e7749a schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N54ca240fb91945409345e1f1c7cf6ec0 schema:issueNumber 4
40 rdf:type schema:PublicationIssue
41 N6809bd186a004c09b477e3e5da2f5f51 schema:name dimensions_id
42 schema:value pub.1027312329
43 rdf:type schema:PropertyValue
44 N7fe3c394514f482c92db36be2e1b24e2 schema:volumeNumber 1
45 rdf:type schema:PublicationVolume
46 N83adff104ee6499d8eff6abe7f91c8c3 rdf:first sg:person.07523205527.24
47 rdf:rest rdf:nil
48 Ncae36c84a23c48109e514af987ccc880 rdf:first sg:person.0674326220.33
49 rdf:rest N83adff104ee6499d8eff6abe7f91c8c3
50 Nd85c5dbe403d4d2aacd6871d1c9400a6 schema:name readcube_id
51 schema:value 821b49c9330d57d09d9c5e7eba7faa8548dedb63dd59d5d1e9309c0f6a1e7c4b
52 rdf:type schema:PropertyValue
53 Nf5f5b6a763db423c8a22506224b8c32f schema:name doi
54 schema:value 10.1007/bf02187705
55 rdf:type schema:PropertyValue
56 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
57 schema:name Mathematical Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
60 schema:name Pure Mathematics
61 rdf:type schema:DefinedTerm
62 sg:journal.1043660 schema:issn 0179-5376
63 1432-0444
64 schema:name Discrete & Computational Geometry
65 rdf:type schema:Periodical
66 sg:person.0674326220.33 schema:affiliation https://www.grid.ac/institutes/grid.35403.31
67 schema:familyName Tamassia
68 schema:givenName Roberto
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
70 rdf:type schema:Person
71 sg:person.07523205527.24 schema:affiliation https://www.grid.ac/institutes/grid.35403.31
72 schema:familyName Tollis
73 schema:givenName Ioannis G.
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07523205527.24
75 rdf:type schema:Person
76 sg:pub.10.1007/978-1-349-03521-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109703686
77 https://doi.org/10.1007/978-1-349-03521-2
78 rdf:type schema:CreativeWork
79 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
80 https://doi.org/10.1007/bf02187706
81 rdf:type schema:CreativeWork
82 https://app.dimensions.ai/details/publication/pub.1109703686 schema:CreativeWork
83 https://doi.org/10.1002/net.3230140202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023775252
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1016/0012-365x(83)90128-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041600793
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1016/0304-3975(76)90086-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035496339
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1090/s0002-9947-1956-0081471-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015583804
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1137/0211042 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841658
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1145/323233.323253 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002612669
96 rdf:type schema:CreativeWork
97 https://www.grid.ac/institutes/grid.35403.31 schema:alternateName University of Illinois at Urbana Champaign
98 schema:name Coordinated Science Laboratory and Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, IL, USA
99 Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, 61801, Urbana, IL, USA
100 rdf:type schema:Organization
 




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


...