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": "2022-01-01T18:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/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 Nd051a37113194a4ab131742971566dd4
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 N27389324486d421fa7be75b9bb89115a
11 N72534854af5447bda1d54a8e631ba107
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 Na0d1a72331f94ee2b9e8dffe3e6ea116
52 Ncbe01f05a6b549bda1bd6b01d028cb77
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006609987
54 https://doi.org/10.1007/s00453-003-1055-0
55 schema:sdDatePublished 2022-01-01T18:12
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Naff88e67d39d4dc487abc813ed6ae328
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 N27389324486d421fa7be75b9bb89115a schema:volumeNumber 38
63 rdf:type schema:PublicationVolume
64 N72534854af5447bda1d54a8e631ba107 schema:issueNumber 4
65 rdf:type schema:PublicationIssue
66 N99cda3cd44e5474889bc3e0a8ce15bfa rdf:first sg:person.011352641523.42
67 rdf:rest rdf:nil
68 Na0d1a72331f94ee2b9e8dffe3e6ea116 schema:name dimensions_id
69 schema:value pub.1006609987
70 rdf:type schema:PropertyValue
71 Naff88e67d39d4dc487abc813ed6ae328 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 Ncbe01f05a6b549bda1bd6b01d028cb77 schema:name doi
74 schema:value 10.1007/s00453-003-1055-0
75 rdf:type schema:PropertyValue
76 Nd051a37113194a4ab131742971566dd4 rdf:first sg:person.015654265661.98
77 rdf:rest N99cda3cd44e5474889bc3e0a8ce15bfa
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)


...