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

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 N0140b97d0b084f63aae2d8e0fec12492
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 Nc3d6553589d54f5ab0a9509e5e0e4392
21 Nfb6c9e0c84564a34b3ff6cfa6a7ec584
22 sg:journal.1043660
23 schema:name A unified approach to visibility representations of planar graphs
24 schema:pagination 321-341
25 schema:productId Nb2a80e70933641c88822a70845eff6ea
26 Nc8253290cd5a4b97b24ee797057578e9
27 Ndbb208ef7cfd4c689ef3e7a48b7c5b1f
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 Nf22871dd56d74a54b46ba08afa9ed94b
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 N0140b97d0b084f63aae2d8e0fec12492 rdf:first sg:person.0674326220.33
38 rdf:rest Nf2817c0c7d2d4f8f8ea1f2d24f72a6ee
39 Nb2a80e70933641c88822a70845eff6ea schema:name doi
40 schema:value 10.1007/bf02187705
41 rdf:type schema:PropertyValue
42 Nc3d6553589d54f5ab0a9509e5e0e4392 schema:volumeNumber 1
43 rdf:type schema:PublicationVolume
44 Nc8253290cd5a4b97b24ee797057578e9 schema:name readcube_id
45 schema:value 821b49c9330d57d09d9c5e7eba7faa8548dedb63dd59d5d1e9309c0f6a1e7c4b
46 rdf:type schema:PropertyValue
47 Ndbb208ef7cfd4c689ef3e7a48b7c5b1f schema:name dimensions_id
48 schema:value pub.1027312329
49 rdf:type schema:PropertyValue
50 Nf22871dd56d74a54b46ba08afa9ed94b schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 Nf2817c0c7d2d4f8f8ea1f2d24f72a6ee rdf:first sg:person.07523205527.24
53 rdf:rest rdf:nil
54 Nfb6c9e0c84564a34b3ff6cfa6a7ec584 schema:issueNumber 4
55 rdf:type schema:PublicationIssue
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)


...