Recognizing Hole-Free 4-Map Graphs in Cubic Time View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2006-02-10

AUTHORS

Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou

ABSTRACT

We present a cubic-time algorithm for the following problem: Given a simple graph, decide whether it is realized by adjacencies of countries in a map without holes, in which at most four countries meet at any point.

PAGES

227-262

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-005-1184-8

DOI

http://dx.doi.org/10.1007/s00453-005-1184-8

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo 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 Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA", 
          "id": "http://www.grid.ac/institutes/grid.189967.8", 
          "name": [
            "Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grigni", 
        "givenName": "Michelangelo", 
        "id": "sg:person.0622227534.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0622227534.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California at Berkeley, Berkeley, CA 94720, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California at Berkeley, Berkeley, CA 94720, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006-02-10", 
    "datePublishedReg": "2006-02-10", 
    "description": "We present a cubic-time algorithm for the following problem: Given a simple graph, decide whether it is realized by adjacencies of countries in a map without holes, in which at most four countries meet at any point.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-005-1184-8", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "45"
      }
    ], 
    "keywords": [
      "countries", 
      "time", 
      "point", 
      "problem", 
      "maps", 
      "holes", 
      "simple graph", 
      "adjacency", 
      "algorithm", 
      "graph", 
      "cubic time", 
      "cubic-time algorithm", 
      "adjacencies of countries", 
      "Hole-Free 4-Map Graphs"
    ], 
    "name": "Recognizing Hole-Free 4-Map Graphs in Cubic Time", 
    "pagination": "227-262", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048829130"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-005-1184-8"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-005-1184-8", 
      "https://app.dimensions.ai/details/publication/pub.1048829130"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-11-01T18:09", 
    "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_428.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-005-1184-8"
  }
]
 

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-005-1184-8'

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-005-1184-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-005-1184-8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-005-1184-8'


 

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

84 TRIPLES      20 PREDICATES      37 URIs      31 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-005-1184-8 schema:author Nf5afcb53dd9a4f14ae0df707324f9d24
2 schema:datePublished 2006-02-10
3 schema:datePublishedReg 2006-02-10
4 schema:description We present a cubic-time algorithm for the following problem: Given a simple graph, decide whether it is realized by adjacencies of countries in a map without holes, in which at most four countries meet at any point.
5 schema:genre article
6 schema:inLanguage en
7 schema:isAccessibleForFree true
8 schema:isPartOf Nc4e3bdaba2624b4a86f0bbc444acb61d
9 Ndbdd60076eb1414baa20e09aa5488631
10 sg:journal.1047644
11 schema:keywords Hole-Free 4-Map Graphs
12 adjacencies of countries
13 adjacency
14 algorithm
15 countries
16 cubic time
17 cubic-time algorithm
18 graph
19 holes
20 maps
21 point
22 problem
23 simple graph
24 time
25 schema:name Recognizing Hole-Free 4-Map Graphs in Cubic Time
26 schema:pagination 227-262
27 schema:productId N9f3a0914a2724d58a0ba733f21009b81
28 Nefd218755f454b239dea217da72172c1
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048829130
30 https://doi.org/10.1007/s00453-005-1184-8
31 schema:sdDatePublished 2021-11-01T18:09
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher Na2f16157eff84877bf638c69caaa5021
34 schema:url https://doi.org/10.1007/s00453-005-1184-8
35 sgo:license sg:explorer/license/
36 sgo:sdDataset articles
37 rdf:type schema:ScholarlyArticle
38 N907486b825c140648d0909f2366d230e rdf:first sg:person.0622227534.36
39 rdf:rest Ncc0099c2aefc4dbab633f7b90b2a71f3
40 N9f3a0914a2724d58a0ba733f21009b81 schema:name doi
41 schema:value 10.1007/s00453-005-1184-8
42 rdf:type schema:PropertyValue
43 Na2f16157eff84877bf638c69caaa5021 schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 Nc4e3bdaba2624b4a86f0bbc444acb61d schema:volumeNumber 45
46 rdf:type schema:PublicationVolume
47 Ncc0099c2aefc4dbab633f7b90b2a71f3 rdf:first sg:person.013233165465.63
48 rdf:rest rdf:nil
49 Ndbdd60076eb1414baa20e09aa5488631 schema:issueNumber 2
50 rdf:type schema:PublicationIssue
51 Nefd218755f454b239dea217da72172c1 schema:name dimensions_id
52 schema:value pub.1048829130
53 rdf:type schema:PropertyValue
54 Nf5afcb53dd9a4f14ae0df707324f9d24 rdf:first sg:person.015654265661.98
55 rdf:rest N907486b825c140648d0909f2366d230e
56 sg:journal.1047644 schema:issn 0178-4617
57 1432-0541
58 schema:name Algorithmica
59 schema:publisher Springer Nature
60 rdf:type schema:Periodical
61 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
62 schema:familyName Papadimitriou
63 schema:givenName Christos H.
64 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
65 rdf:type schema:Person
66 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
67 schema:familyName Chen
68 schema:givenName Zhi-Zhong
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
70 rdf:type schema:Person
71 sg:person.0622227534.36 schema:affiliation grid-institutes:grid.189967.8
72 schema:familyName Grigni
73 schema:givenName Michelangelo
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0622227534.36
75 rdf:type schema:Person
76 grid-institutes:grid.189967.8 schema:alternateName Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA
77 schema:name Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA
78 rdf:type schema:Organization
79 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
80 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
81 rdf:type schema:Organization
82 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California at Berkeley, Berkeley, CA 94720, USA
83 schema:name Computer Science Division, University of California at Berkeley, Berkeley, CA 94720, USA
84 rdf:type schema:Organization
 




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


...