A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-08-02

AUTHORS

Xin He

ABSTRACT

In this paper we introduce a new drawing style of a plane graph G, called proper box rectangular (PBR) drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem. More... »

PAGES

234-245

Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-42423-9
978-3-540-44634-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44634-6_22

DOI

http://dx.doi.org/10.1007/3-540-44634-6_22

DIMENSIONS

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


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/16", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Studies in Human Society", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1606", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Political Science", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, 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 and Engineering, 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": "2001-08-02", 
    "datePublishedReg": "2001-08-02", 
    "description": "In this paper we introduce a new drawing style of a plane graph G, called proper box rectangular (PBR) drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44634-6_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42423-9", 
        "978-3-540-44634-7"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "paper", 
      "style", 
      "drawings", 
      "face", 
      "such drawings", 
      "Rahman", 
      "box", 
      "conditions", 
      "Nakano", 
      "problem", 
      "rectangle", 
      "edge", 
      "vertical line segments", 
      "line segments", 
      "segments", 
      "sufficient conditions", 
      "simple linear time algorithm", 
      "linear time algorithm", 
      "time algorithm", 
      "algorithm", 
      "Nishizeki", 
      "method", 
      "new algorithm", 
      "drawing problem", 
      "graph", 
      "plane graph G", 
      "graph G", 
      "proper box rectangular (PBR) drawing", 
      "box rectangular (PBR) drawing", 
      "rectangular drawing", 
      "vertices", 
      "PBR drawing", 
      "BR drawing problem", 
      "plane graph"
    ], 
    "name": "A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs", 
    "pagination": "234-245", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012674528"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44634-6_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44634-6_22", 
      "https://app.dimensions.ai/details/publication/pub.1012674528"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:57", 
    "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_352.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44634-6_22"
  }
]
 

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-44634-6_22'

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-44634-6_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44634-6_22'

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-44634-6_22'


 

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

104 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44634-6_22 schema:about anzsrc-for:16
2 anzsrc-for:1606
3 schema:author Ncf6edf88352d4fadb31bd5366b3ca79e
4 schema:datePublished 2001-08-02
5 schema:datePublishedReg 2001-08-02
6 schema:description In this paper we introduce a new drawing style of a plane graph G, called proper box rectangular (PBR) drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem.
7 schema:editor N0c982d0388b54b9daeeb686231a455a9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nd9148a4f478e4f70b084c8a8dbce6598
12 schema:keywords BR drawing problem
13 Nakano
14 Nishizeki
15 PBR drawing
16 Rahman
17 algorithm
18 box
19 box rectangular (PBR) drawing
20 conditions
21 drawing problem
22 drawings
23 edge
24 face
25 graph
26 graph G
27 line segments
28 linear time algorithm
29 method
30 new algorithm
31 paper
32 plane graph
33 plane graph G
34 problem
35 proper box rectangular (PBR) drawing
36 rectangle
37 rectangular drawing
38 segments
39 simple linear time algorithm
40 style
41 such drawings
42 sufficient conditions
43 time algorithm
44 vertical line segments
45 vertices
46 schema:name A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs
47 schema:pagination 234-245
48 schema:productId N63c8c14922654b1fa2d20df7bc4b35ec
49 Nc584ecc6a1af4a45baf432cc8f15207a
50 schema:publisher Nc54c1dc515b84e54a18c42376af7958c
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012674528
52 https://doi.org/10.1007/3-540-44634-6_22
53 schema:sdDatePublished 2021-11-01T18:57
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Na7e6b1b1f8cb4210b2d823e4f878907d
56 schema:url https://doi.org/10.1007/3-540-44634-6_22
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N0c982d0388b54b9daeeb686231a455a9 rdf:first N0d3f70862c174496a5c3c23caa00c2cc
61 rdf:rest N4f7c422d0ed5412fbd2cc86f516b4f59
62 N0d3f70862c174496a5c3c23caa00c2cc schema:familyName Dehne
63 schema:givenName Frank
64 rdf:type schema:Person
65 N4f7c422d0ed5412fbd2cc86f516b4f59 rdf:first Nf1f7befb55af4e6b97ab43a91efb6276
66 rdf:rest Nc22b2f19a29d4dd6b10971baff82303e
67 N63c8c14922654b1fa2d20df7bc4b35ec schema:name dimensions_id
68 schema:value pub.1012674528
69 rdf:type schema:PropertyValue
70 N9013bc18ad9b47959af426bee13b53dd schema:familyName Tamassia
71 schema:givenName Roberto
72 rdf:type schema:Person
73 Na7e6b1b1f8cb4210b2d823e4f878907d schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 Nc22b2f19a29d4dd6b10971baff82303e rdf:first N9013bc18ad9b47959af426bee13b53dd
76 rdf:rest rdf:nil
77 Nc54c1dc515b84e54a18c42376af7958c schema:name Springer Nature
78 rdf:type schema:Organisation
79 Nc584ecc6a1af4a45baf432cc8f15207a schema:name doi
80 schema:value 10.1007/3-540-44634-6_22
81 rdf:type schema:PropertyValue
82 Ncf6edf88352d4fadb31bd5366b3ca79e rdf:first sg:person.011352641523.42
83 rdf:rest rdf:nil
84 Nd9148a4f478e4f70b084c8a8dbce6598 schema:isbn 978-3-540-42423-9
85 978-3-540-44634-7
86 schema:name Algorithms and Data Structures
87 rdf:type schema:Book
88 Nf1f7befb55af4e6b97ab43a91efb6276 schema:familyName Sack
89 schema:givenName Jörg-Rüdiger
90 rdf:type schema:Person
91 anzsrc-for:16 schema:inDefinedTermSet anzsrc-for:
92 schema:name Studies in Human Society
93 rdf:type schema:DefinedTerm
94 anzsrc-for:1606 schema:inDefinedTermSet anzsrc-for:
95 schema:name Political Science
96 rdf:type schema:DefinedTerm
97 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
98 schema:familyName He
99 schema:givenName Xin
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
101 rdf:type schema:Person
102 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
103 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
104 rdf:type schema:Organization
 




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


...