General theoretical results on rectilinear embedability of graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1991-04

AUTHORS

Yanpei Liu, A. Morgana, B. Simeone

ABSTRACT

In the design of certain kinds of electronic circuits the following question arises: given a non-negative integerk, what graphs admit of a plane embedding such that every edge is a broken line formed by horizontal and vertical segments and having at mostk bends? Any such graph is said to bek-rectilinear. No matter whatk is, an obvious necessary condition fork-rectilinearity is that the degree of each vertex does not exceed four. Our main result is that every planar graphH satisfying this condition is 3-rectilinear: in fact, it is 2-rectilinear with the only exception of the octahedron. We also outline a polynomial-time algorithm which actually constructs a plane embedding ofH with at most 2 bends (3 bends ifH is the octahedron) on each edge. The resulting embedding has the property that the total number of bends does not exceed 2n, wheren is the number of vertices ofH. More... »

PAGES

187-192

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Chinese Academy of Sciences", 
          "id": "https://www.grid.ac/institutes/grid.9227.e", 
          "name": [
            "Institute of Applied Mathematics & Institute of Mathematics, Academia Sinica, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Yanpei", 
        "id": "sg:person.010340445102.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010340445102.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Morgana", 
        "givenName": "A.", 
        "id": "sg:person.010141153531.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010141153531.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simeone", 
        "givenName": "B.", 
        "id": "sg:person.012600006066.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1991-04", 
    "datePublishedReg": "1991-04-01", 
    "description": "In the design of certain kinds of electronic circuits the following question arises: given a non-negative integerk, what graphs admit of a plane embedding such that every edge is a broken line formed by horizontal and vertical segments and having at mostk bends? Any such graph is said to bek-rectilinear. No matter whatk is, an obvious necessary condition fork-rectilinearity is that the degree of each vertex does not exceed four. Our main result is that every planar graphH satisfying this condition is 3-rectilinear: in fact, it is 2-rectilinear with the only exception of the octahedron. We also outline a polynomial-time algorithm which actually constructs a plane embedding ofH with at most 2 bends (3 bends ifH is the octahedron) on each edge. The resulting embedding has the property that the total number of bends does not exceed 2n, wheren is the number of vertices ofH.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02006104", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1041650", 
        "issn": [
          "0168-9673", 
          "1618-3932"
        ], 
        "name": "Acta Mathematicae Applicatae Sinica, English Series", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "7"
      }
    ], 
    "name": "General theoretical results on rectilinear embedability of graphs", 
    "pagination": "187-192", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "1e1f17a741776651d5a16077284a9a63c4a3a06dbee6e350340a8c0d2a99cf68"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02006104"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006323737"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02006104", 
      "https://app.dimensions.ai/details/publication/pub.1006323737"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T19:05", 
    "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_8678_00000498.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF02006104"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

78 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02006104 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N478008ceddab424791832fc489c2b024
4 schema:datePublished 1991-04
5 schema:datePublishedReg 1991-04-01
6 schema:description In the design of certain kinds of electronic circuits the following question arises: given a non-negative integerk, what graphs admit of a plane embedding such that every edge is a broken line formed by horizontal and vertical segments and having at mostk bends? Any such graph is said to bek-rectilinear. No matter whatk is, an obvious necessary condition fork-rectilinearity is that the degree of each vertex does not exceed four. Our main result is that every planar graphH satisfying this condition is 3-rectilinear: in fact, it is 2-rectilinear with the only exception of the octahedron. We also outline a polynomial-time algorithm which actually constructs a plane embedding ofH with at most 2 bends (3 bends ifH is the octahedron) on each edge. The resulting embedding has the property that the total number of bends does not exceed 2n, wheren is the number of vertices ofH.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N655c26bac0f94adba2670be8d9713b2b
11 Ncdb6ed53b5974543998611b333317346
12 sg:journal.1041650
13 schema:name General theoretical results on rectilinear embedability of graphs
14 schema:pagination 187-192
15 schema:productId N0286fb55047644daae7e5b29859422da
16 N148e8a4098a247bf8e2236563d4f9d04
17 Ne2011de740c440cebdaac97dae0ea772
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006323737
19 https://doi.org/10.1007/bf02006104
20 schema:sdDatePublished 2019-04-10T19:05
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N7e78a528867a4e57bfad6fec6575ff40
23 schema:url http://link.springer.com/10.1007/BF02006104
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N0286fb55047644daae7e5b29859422da schema:name readcube_id
28 schema:value 1e1f17a741776651d5a16077284a9a63c4a3a06dbee6e350340a8c0d2a99cf68
29 rdf:type schema:PropertyValue
30 N148e8a4098a247bf8e2236563d4f9d04 schema:name dimensions_id
31 schema:value pub.1006323737
32 rdf:type schema:PropertyValue
33 N478008ceddab424791832fc489c2b024 rdf:first sg:person.010340445102.62
34 rdf:rest N772d8ff49b414dbcbc06029566dc23f7
35 N6489353cbe9b452e9079303d2285d53f rdf:first sg:person.012600006066.78
36 rdf:rest rdf:nil
37 N655c26bac0f94adba2670be8d9713b2b schema:issueNumber 2
38 rdf:type schema:PublicationIssue
39 N772d8ff49b414dbcbc06029566dc23f7 rdf:first sg:person.010141153531.51
40 rdf:rest N6489353cbe9b452e9079303d2285d53f
41 N7e78a528867a4e57bfad6fec6575ff40 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 Ncdb6ed53b5974543998611b333317346 schema:volumeNumber 7
44 rdf:type schema:PublicationVolume
45 Ne2011de740c440cebdaac97dae0ea772 schema:name doi
46 schema:value 10.1007/bf02006104
47 rdf:type schema:PropertyValue
48 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
49 schema:name Information and Computing Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
52 schema:name Computation Theory and Mathematics
53 rdf:type schema:DefinedTerm
54 sg:journal.1041650 schema:issn 0168-9673
55 1618-3932
56 schema:name Acta Mathematicae Applicatae Sinica, English Series
57 rdf:type schema:Periodical
58 sg:person.010141153531.51 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
59 schema:familyName Morgana
60 schema:givenName A.
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010141153531.51
62 rdf:type schema:Person
63 sg:person.010340445102.62 schema:affiliation https://www.grid.ac/institutes/grid.9227.e
64 schema:familyName Liu
65 schema:givenName Yanpei
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010340445102.62
67 rdf:type schema:Person
68 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
69 schema:familyName Simeone
70 schema:givenName B.
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
72 rdf:type schema:Person
73 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
74 schema:name Università di Roma “La Sapienza”, Italy
75 rdf:type schema:Organization
76 https://www.grid.ac/institutes/grid.9227.e schema:alternateName Chinese Academy of Sciences
77 schema:name Institute of Applied Mathematics & Institute of Mathematics, Academia Sinica, China
78 rdf:type schema:Organization
 




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


...