Monotone Drawings of 3-Connected Plane Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-11-12

AUTHORS

Xin He , Dayu He

ABSTRACT

A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone on some line luw. (Namely, the order of the orthogonal projections of the vertices in Puw on luw is the same as the order they appear in Puw.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f ×f (f ≤ 2n − 5 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line luw can be identified in O(1) time. More... »

PAGES

729-741

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_61

DOI

http://dx.doi.org/10.1007/978-3-662-48350-3_61

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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"
      }, 
      {
        "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": "Dayu", 
        "id": "sg:person.011772764733.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011772764733.17"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-11-12", 
    "datePublishedReg": "2015-11-12", 
    "description": "A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone on some line luw. (Namely, the order of the orthogonal projections of the vertices in Puw on luw is the same as the order they appear in Puw.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f \u00d7f (f\u2009\u2264\u20092n\u2009\u2212\u20095 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line luw can be identified in O(1) time.", 
    "editor": [
      {
        "familyName": "Bansal", 
        "givenName": "Nikhil", 
        "type": "Person"
      }, 
      {
        "familyName": "Finocchi", 
        "givenName": "Irene", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48350-3_61", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48349-7", 
        "978-3-662-48350-3"
      ], 
      "name": "Algorithms - ESA 2015", 
      "type": "Book"
    }, 
    "keywords": [
      "monotone drawing", 
      "graph", 
      "straight-line drawing", 
      "plane graph", 
      "drawings", 
      "graph G", 
      "grid", 
      "vertices u", 
      "advantages", 
      "time", 
      "monotone", 
      "pairs", 
      "luw", 
      "paper", 
      "\u00d7F", 
      "path Puw", 
      "PUWs", 
      "line luw", 
      "classical Schnyder drawing", 
      "Schnyder drawing", 
      "size f \u00d7f", 
      "f \u00d7f", 
      "monotone line luw"
    ], 
    "name": "Monotone Drawings of 3-Connected Plane Graphs", 
    "pagination": "729-741", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001861769"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48350-3_61"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48350-3_61", 
      "https://app.dimensions.ai/details/publication/pub.1001861769"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:50", 
    "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_193.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48350-3_61"
  }
]
 

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/978-3-662-48350-3_61'

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/978-3-662-48350-3_61'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_61'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48350-3_61'


 

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

95 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48350-3_61 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Nf1020b8c9ea143778bbef78de7b80e34
4 schema:datePublished 2015-11-12
5 schema:datePublishedReg 2015-11-12
6 schema:description A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone on some line luw. (Namely, the order of the orthogonal projections of the vertices in Puw on luw is the same as the order they appear in Puw.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f ×f (f ≤ 2n − 5 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line luw can be identified in O(1) time.
7 schema:editor N5dd6ced7dbb94a88bbdae01af8172dbb
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne618908e44a0498f8709e3d4772c662d
12 schema:keywords PUWs
13 Schnyder drawing
14 advantages
15 classical Schnyder drawing
16 drawings
17 f ×f
18 graph
19 graph G
20 grid
21 line luw
22 luw
23 monotone
24 monotone drawing
25 monotone line luw
26 pairs
27 paper
28 path Puw
29 plane graph
30 size f ×f
31 straight-line drawing
32 time
33 vertices u
34 ×F
35 schema:name Monotone Drawings of 3-Connected Plane Graphs
36 schema:pagination 729-741
37 schema:productId N5ab14bba759a4586aa186c725a752b60
38 N922027e1d0124708be9c8ad1cd365ba1
39 schema:publisher N9b2cd64a46f244f8b0429fe4dff01ba3
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001861769
41 https://doi.org/10.1007/978-3-662-48350-3_61
42 schema:sdDatePublished 2021-11-01T18:50
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher N15dee1bf3b1849beaabd771a70089adf
45 schema:url https://doi.org/10.1007/978-3-662-48350-3_61
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N15dee1bf3b1849beaabd771a70089adf schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N205d2704bc234d7fa2f18dad8b17bedc rdf:first N25273cf67c0642e598b565de4f571450
52 rdf:rest rdf:nil
53 N25273cf67c0642e598b565de4f571450 schema:familyName Finocchi
54 schema:givenName Irene
55 rdf:type schema:Person
56 N32ce8578b0b84e8d924f7f57bca1ea30 schema:familyName Bansal
57 schema:givenName Nikhil
58 rdf:type schema:Person
59 N5ab14bba759a4586aa186c725a752b60 schema:name dimensions_id
60 schema:value pub.1001861769
61 rdf:type schema:PropertyValue
62 N5dd6ced7dbb94a88bbdae01af8172dbb rdf:first N32ce8578b0b84e8d924f7f57bca1ea30
63 rdf:rest N205d2704bc234d7fa2f18dad8b17bedc
64 N922027e1d0124708be9c8ad1cd365ba1 schema:name doi
65 schema:value 10.1007/978-3-662-48350-3_61
66 rdf:type schema:PropertyValue
67 N9b2cd64a46f244f8b0429fe4dff01ba3 schema:name Springer Nature
68 rdf:type schema:Organisation
69 Ne618908e44a0498f8709e3d4772c662d schema:isbn 978-3-662-48349-7
70 978-3-662-48350-3
71 schema:name Algorithms - ESA 2015
72 rdf:type schema:Book
73 Nf1020b8c9ea143778bbef78de7b80e34 rdf:first sg:person.011352641523.42
74 rdf:rest Nfaa75d33bef345f2bf62d8057c188d31
75 Nfaa75d33bef345f2bf62d8057c188d31 rdf:first sg:person.011772764733.17
76 rdf:rest rdf:nil
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information Systems
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.011772764733.17 schema:affiliation grid-institutes:grid.273335.3
89 schema:familyName He
90 schema:givenName Dayu
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011772764733.17
92 rdf:type schema:Person
93 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
94 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
95 rdf:type schema:Organization
 




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


...