Disk Embeddings of Planar Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2003-12-05

AUTHORS

Zhi-Zhong Chen, Xin He

ABSTRACT

Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$ with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$ satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of ${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve $\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$ but contains no other leaves of ${\FF}$. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces a connected subgraph of $G$. More... »

PAGES

539-576

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-003-1055-0

DOI

http://dx.doi.org/10.1007/s00453-003-1055-0

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences,\n\tTokyo Denki University, Hatoyama, Saitama 350-0394, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences,\n\tTokyo Denki University, Hatoyama, Saitama 350-0394, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, State Univeristy of New York at Buffalo, Buffalo, NY\n14260, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, State Univeristy of New York at Buffalo, Buffalo, NY\n14260, 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": "2003-12-05", 
    "datePublishedReg": "2003-12-05", 
    "description": "Abstract \nGiven a planar graph $G=(V,E)$ and a rooted forest ${\\FF}=(V_{\\FF}, A_{\\FF})$ \nwith leaf set $V$, we wish to decide whether $G$ has a plane embedding $\\GG$ \nsatisfying the following condition: There are $|V_{\\FF}|-|V|$ pairwise noncrossing \nJordan curves in the plane one-to-one corresponding to the nonleaf vertices of \n${\\FF}$ such that for every nonleaf vertex $f$ of ${\\FF}$, the interior of the curve \n$\\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\\FF}$\nbut contains no other leaves of ${\\FF}$. \nThis problem arises from theoretical studies in geographic database systems. \nIt is unknown whether this problem can be solved in polynomial time. \nThis paper presents an almost linear-time algorithm for a nontrivial special case \nwhere the set of leaf descendants of each nonleaf vertex $f$ in ${\\FF}$ induces \na connected subgraph of $G$.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-003-1055-0", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "38"
      }
    ], 
    "keywords": [
      "geographic database systems", 
      "linear-time algorithm", 
      "nonleaf vertices", 
      "database systems", 
      "planar graphs", 
      "polynomial time", 
      "connected subgraph", 
      "graph", 
      "vertices", 
      "algorithm", 
      "nontrivial special case", 
      "embedding", 
      "subgraphs", 
      "set", 
      "special case", 
      "system", 
      "pairwise", 
      "one", 
      "time", 
      "plane", 
      "cases", 
      "forest", 
      "following condition", 
      "curves", 
      "conditions", 
      "descendants", 
      "Jordan", 
      "study", 
      "interior", 
      "theoretical study", 
      "leaves", 
      "plane one", 
      "problem", 
      "paper", 
      "leaf descendants", 
      "Disk Embeddings"
    ], 
    "name": "Disk Embeddings of Planar Graphs", 
    "pagination": "539-576", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006609987"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-003-1055-0"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-003-1055-0", 
      "https://app.dimensions.ai/details/publication/pub.1006609987"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-11-01T18:06", 
    "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/article/article_371.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-003-1055-0"
  }
]
 

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/s00453-003-1055-0'

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/s00453-003-1055-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1055-0'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1055-0'


 

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

104 TRIPLES      21 PREDICATES      61 URIs      53 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-003-1055-0 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ne6363e0778354532a8e6816fc240da59
4 schema:datePublished 2003-12-05
5 schema:datePublishedReg 2003-12-05
6 schema:description Abstract Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$ with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$ satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of ${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve $\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$ but contains no other leaves of ${\FF}$. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces a connected subgraph of $G$.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N39b79370e8a34cc2bd70f719fb4ef000
11 Nd18d355f41df4790ac7d076625586498
12 sg:journal.1047644
13 schema:keywords Disk Embeddings
14 Jordan
15 algorithm
16 cases
17 conditions
18 connected subgraph
19 curves
20 database systems
21 descendants
22 embedding
23 following condition
24 forest
25 geographic database systems
26 graph
27 interior
28 leaf descendants
29 leaves
30 linear-time algorithm
31 nonleaf vertices
32 nontrivial special case
33 one
34 pairwise
35 paper
36 planar graphs
37 plane
38 plane one
39 polynomial time
40 problem
41 set
42 special case
43 study
44 subgraphs
45 system
46 theoretical study
47 time
48 vertices
49 schema:name Disk Embeddings of Planar Graphs
50 schema:pagination 539-576
51 schema:productId N3e74c6cf9ab94fdeb7161806e8d4a590
52 Nd241b30cab8243efb89b7dac418909d5
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006609987
54 https://doi.org/10.1007/s00453-003-1055-0
55 schema:sdDatePublished 2021-11-01T18:06
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N1246dd23d2434e3a9eca667008e5e20e
58 schema:url https://doi.org/10.1007/s00453-003-1055-0
59 sgo:license sg:explorer/license/
60 sgo:sdDataset articles
61 rdf:type schema:ScholarlyArticle
62 N1246dd23d2434e3a9eca667008e5e20e schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N39b79370e8a34cc2bd70f719fb4ef000 schema:issueNumber 4
65 rdf:type schema:PublicationIssue
66 N3e74c6cf9ab94fdeb7161806e8d4a590 schema:name doi
67 schema:value 10.1007/s00453-003-1055-0
68 rdf:type schema:PropertyValue
69 Nb7488b81ca3b4820ba4742e1d7466b47 rdf:first sg:person.011352641523.42
70 rdf:rest rdf:nil
71 Nd18d355f41df4790ac7d076625586498 schema:volumeNumber 38
72 rdf:type schema:PublicationVolume
73 Nd241b30cab8243efb89b7dac418909d5 schema:name dimensions_id
74 schema:value pub.1006609987
75 rdf:type schema:PropertyValue
76 Ne6363e0778354532a8e6816fc240da59 rdf:first sg:person.015654265661.98
77 rdf:rest Nb7488b81ca3b4820ba4742e1d7466b47
78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
79 schema:name Mathematical Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
82 schema:name Pure Mathematics
83 rdf:type schema:DefinedTerm
84 sg:journal.1047644 schema:issn 0178-4617
85 1432-0541
86 schema:name Algorithmica
87 schema:publisher Springer Nature
88 rdf:type schema:Periodical
89 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
90 schema:familyName He
91 schema:givenName Xin
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
93 rdf:type schema:Person
94 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
95 schema:familyName Chen
96 schema:givenName Zhi-Zhong
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
98 rdf:type schema:Person
99 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State Univeristy of New York at Buffalo, Buffalo, NY 14260, USA
100 schema:name Department of Computer Science and Engineering, State Univeristy of New York at Buffalo, Buffalo, NY 14260, USA
101 rdf:type schema:Organization
102 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
103 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
104 rdf:type schema:Organization
 




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


...