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": "2022-01-01T18:16", 
    "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_415.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 Ne9c6822e8e6a45aabe25dc02495afa64
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 N0a4e91eb61044647b91833e1dab26f1a
9 Ndcd5b097435e4b938262a53e4e114c82
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 N5a5001dbba4643bb87891e9180d4aca3
28 Nc34bed1f5a724084864f8d41bb96e103
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048829130
30 https://doi.org/10.1007/s00453-005-1184-8
31 schema:sdDatePublished 2022-01-01T18:16
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N038dec88b42641ac88f6c3c54ae9241d
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 N038dec88b42641ac88f6c3c54ae9241d schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N0a4e91eb61044647b91833e1dab26f1a schema:issueNumber 2
41 rdf:type schema:PublicationIssue
42 N0d19191da6e24a5f9a8b2c249b91417d rdf:first sg:person.013233165465.63
43 rdf:rest rdf:nil
44 N5a5001dbba4643bb87891e9180d4aca3 schema:name doi
45 schema:value 10.1007/s00453-005-1184-8
46 rdf:type schema:PropertyValue
47 Nc34bed1f5a724084864f8d41bb96e103 schema:name dimensions_id
48 schema:value pub.1048829130
49 rdf:type schema:PropertyValue
50 Ndcd5b097435e4b938262a53e4e114c82 schema:volumeNumber 45
51 rdf:type schema:PublicationVolume
52 Ne9c6822e8e6a45aabe25dc02495afa64 rdf:first sg:person.015654265661.98
53 rdf:rest Nf8573162c3ec40dcba32c4b5d430463e
54 Nf8573162c3ec40dcba32c4b5d430463e rdf:first sg:person.0622227534.36
55 rdf:rest N0d19191da6e24a5f9a8b2c249b91417d
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)


...