A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2005-02-07

AUTHORS

Zhi-Zhong Chen, Mitsuharu Kouno

ABSTRACT

A graph G is 1-planar if it can be embedded in the plane in such a way that each edge crosses at most one other edge. Borodin showed that 1-planar graphs are 6-colorable, but his proof does not lead to a linear-time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-plane graphs (which are 1-planar graphs already embedded in the plane). The main difficulty in the design of our algorithm comes from the fact that the class of 1-planar graphs is not closed under the operation of edge contraction. This difficulty is overcome by a structural lemma that may be useful in other problems on 1-planar graphs. This paper also shows that it is NP-complete to decide whether a given 1-planar graph is 4-colorable. The complexity of the problem of deciding whether a given 1-planar graph is 5-colorable is still unknown. More... »

PAGES

147-177

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-004-1134-x

DOI

http://dx.doi.org/10.1007/s00453-004-1134-x

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "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 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": "Kouno", 
        "givenName": "Mitsuharu", 
        "id": "sg:person.011235103317.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011235103317.37"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005-02-07", 
    "datePublishedReg": "2005-02-07", 
    "description": "A graph G is 1-planar if it can be embedded in the plane in such a way \nthat each edge crosses at most one other edge. Borodin showed that \n1-planar graphs are 6-colorable, but his proof does not lead to a linear-time \nalgorithm. This paper presents a linear-time algorithm for 7-coloring \n1-plane graphs (which are 1-planar graphs already embedded in the plane). \nThe main difficulty in the design of our algorithm comes from \nthe fact that the class of 1-planar graphs is not closed under the \noperation of edge contraction. This difficulty is overcome by a structural \nlemma that may be useful in other problems on 1-planar graphs. This paper \nalso shows that it is NP-complete to decide whether a given 1-planar graph \nis 4-colorable. The complexity of the problem of deciding whether a given \n1-planar graph is 5-colorable is still unknown.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-004-1134-x", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "43"
      }
    ], 
    "keywords": [
      "linear time algorithm", 
      "graph G", 
      "graph", 
      "edge contraction", 
      "main difficulty", 
      "algorithm", 
      "lemma", 
      "problem", 
      "Borodin", 
      "edge", 
      "proof", 
      "class", 
      "complexity", 
      "plane", 
      "NPs", 
      "difficulties", 
      "operation", 
      "design", 
      "fact", 
      "way", 
      "contraction", 
      "paper"
    ], 
    "name": "A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs", 
    "pagination": "147-177", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018476957"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-004-1134-x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-004-1134-x", 
      "https://app.dimensions.ai/details/publication/pub.1018476957"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-10T09:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_399.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-004-1134-x"
  }
]
 

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-004-1134-x'

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-004-1134-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-004-1134-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-004-1134-x'


 

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

87 TRIPLES      21 PREDICATES      47 URIs      39 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-004-1134-x schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Naa115d984b524883b5dd1b2db726260d
4 schema:datePublished 2005-02-07
5 schema:datePublishedReg 2005-02-07
6 schema:description A graph G is 1-planar if it can be embedded in the plane in such a way that each edge crosses at most one other edge. Borodin showed that 1-planar graphs are 6-colorable, but his proof does not lead to a linear-time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-plane graphs (which are 1-planar graphs already embedded in the plane). The main difficulty in the design of our algorithm comes from the fact that the class of 1-planar graphs is not closed under the operation of edge contraction. This difficulty is overcome by a structural lemma that may be useful in other problems on 1-planar graphs. This paper also shows that it is NP-complete to decide whether a given 1-planar graph is 4-colorable. The complexity of the problem of deciding whether a given 1-planar graph is 5-colorable is still unknown.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N30d54ff8fd564c9da46cc90f0faa3b2d
11 Nc97fca9759da4645830206e4e8fc9534
12 sg:journal.1047644
13 schema:keywords Borodin
14 NPs
15 algorithm
16 class
17 complexity
18 contraction
19 design
20 difficulties
21 edge
22 edge contraction
23 fact
24 graph
25 graph G
26 lemma
27 linear time algorithm
28 main difficulty
29 operation
30 paper
31 plane
32 problem
33 proof
34 way
35 schema:name A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs
36 schema:pagination 147-177
37 schema:productId N45d60cbc0dfa4e3690439cec86c390c2
38 N8545fc0e30124e438be91614f39f033a
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018476957
40 https://doi.org/10.1007/s00453-004-1134-x
41 schema:sdDatePublished 2022-05-10T09:55
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher Nb34f5de6510749ff8c7801f3718a78e3
44 schema:url https://doi.org/10.1007/s00453-004-1134-x
45 sgo:license sg:explorer/license/
46 sgo:sdDataset articles
47 rdf:type schema:ScholarlyArticle
48 N30d54ff8fd564c9da46cc90f0faa3b2d schema:issueNumber 3
49 rdf:type schema:PublicationIssue
50 N45d60cbc0dfa4e3690439cec86c390c2 schema:name dimensions_id
51 schema:value pub.1018476957
52 rdf:type schema:PropertyValue
53 N4622b678b98843d386fdb720742b531d rdf:first sg:person.011235103317.37
54 rdf:rest rdf:nil
55 N8545fc0e30124e438be91614f39f033a schema:name doi
56 schema:value 10.1007/s00453-004-1134-x
57 rdf:type schema:PropertyValue
58 Naa115d984b524883b5dd1b2db726260d rdf:first sg:person.015654265661.98
59 rdf:rest N4622b678b98843d386fdb720742b531d
60 Nb34f5de6510749ff8c7801f3718a78e3 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Nc97fca9759da4645830206e4e8fc9534 schema:volumeNumber 43
63 rdf:type schema:PublicationVolume
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
68 schema:name Computation Theory and Mathematics
69 rdf:type schema:DefinedTerm
70 sg:journal.1047644 schema:issn 0178-4617
71 1432-0541
72 schema:name Algorithmica
73 schema:publisher Springer Nature
74 rdf:type schema:Periodical
75 sg:person.011235103317.37 schema:affiliation grid-institutes:grid.412773.4
76 schema:familyName Kouno
77 schema:givenName Mitsuharu
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011235103317.37
79 rdf:type schema:Person
80 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
81 schema:familyName Chen
82 schema:givenName Zhi-Zhong
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
84 rdf:type schema:Person
85 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
86 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
87 rdf:type schema:Organization
 




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


...