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


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

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 only leads to a complicated polynomial (but nonlinear) time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-planar graphs (that are 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 structure lemma that may find 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

348-357

Book

TITLE

Mathematical Foundations of Computer Science 2003

ISBN

978-3-540-40671-6
978-3-540-45138-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-45138-9_29

DOI

http://dx.doi.org/10.1007/978-3-540-45138-9_29

DIMENSIONS

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


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": "Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-0394, Saitama, 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": "Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-0394, Saitama, 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": "2003", 
    "datePublishedReg": "2003-01-01", 
    "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 only leads to a complicated polynomial (but nonlinear) time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-planar graphs (that are 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 structure lemma that may find 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.", 
    "editor": [
      {
        "familyName": "Rovan", 
        "givenName": "Branislav", 
        "type": "Person"
      }, 
      {
        "familyName": "Vojt\u00e1\u0161", 
        "givenName": "Peter", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-45138-9_29", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40671-6", 
        "978-3-540-45138-9"
      ], 
      "name": "Mathematical Foundations of Computer Science 2003", 
      "type": "Book"
    }, 
    "keywords": [
      "linear time algorithm", 
      "edge crosses", 
      "polynomial time algorithm", 
      "graph G", 
      "graph", 
      "time algorithm", 
      "edge contraction", 
      "main difficulty", 
      "algorithm", 
      "lemma", 
      "problem", 
      "Borodin", 
      "proof", 
      "class", 
      "complexity", 
      "plane", 
      "NPs", 
      "edge", 
      "difficulties", 
      "operation", 
      "design", 
      "fact", 
      "way", 
      "contraction", 
      "cross", 
      "paper"
    ], 
    "name": "A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs", 
    "pagination": "348-357", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030204938"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-45138-9_29"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-45138-9_29", 
      "https://app.dimensions.ai/details/publication/pub.1030204938"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_110.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-45138-9_29"
  }
]
 

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/978-3-540-45138-9_29'

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/978-3-540-45138-9_29'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45138-9_29'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45138-9_29'


 

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

98 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-45138-9_29 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N978656ad8c1b4508ade4b8f5824a482f
4 schema:datePublished 2003
5 schema:datePublishedReg 2003-01-01
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 only leads to a complicated polynomial (but nonlinear) time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-planar graphs (that are 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 structure lemma that may find 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:editor Need487b3386842bfb7eb96dbde19291f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ndcbd752f9f00452fb00806879e3becd7
12 schema:keywords Borodin
13 NPs
14 algorithm
15 class
16 complexity
17 contraction
18 cross
19 design
20 difficulties
21 edge
22 edge contraction
23 edge crosses
24 fact
25 graph
26 graph G
27 lemma
28 linear time algorithm
29 main difficulty
30 operation
31 paper
32 plane
33 polynomial time algorithm
34 problem
35 proof
36 time algorithm
37 way
38 schema:name A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs
39 schema:pagination 348-357
40 schema:productId N023359ddaf604dd982d778ff308cdb7b
41 Nd1bd976184a34eedb429c4afba57f869
42 schema:publisher N5cfab867cffb4e1d9a55077893a211ba
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030204938
44 https://doi.org/10.1007/978-3-540-45138-9_29
45 schema:sdDatePublished 2022-05-20T07:41
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N1c438654dc564267981c27e605927e80
48 schema:url https://doi.org/10.1007/978-3-540-45138-9_29
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N023359ddaf604dd982d778ff308cdb7b schema:name dimensions_id
53 schema:value pub.1030204938
54 rdf:type schema:PropertyValue
55 N0eaab7dc0a4b420483a02f27bbebc304 rdf:first sg:person.011235103317.37
56 rdf:rest rdf:nil
57 N1c438654dc564267981c27e605927e80 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N5cfab867cffb4e1d9a55077893a211ba schema:name Springer Nature
60 rdf:type schema:Organisation
61 N978656ad8c1b4508ade4b8f5824a482f rdf:first sg:person.015654265661.98
62 rdf:rest N0eaab7dc0a4b420483a02f27bbebc304
63 Na2d3ecf07c484f44a1f06c74f6898e85 rdf:first Nb42349cef3a84159aae600d885f5d48e
64 rdf:rest rdf:nil
65 Nb42349cef3a84159aae600d885f5d48e schema:familyName Vojtáš
66 schema:givenName Peter
67 rdf:type schema:Person
68 Nd1bd976184a34eedb429c4afba57f869 schema:name doi
69 schema:value 10.1007/978-3-540-45138-9_29
70 rdf:type schema:PropertyValue
71 Ndcbd752f9f00452fb00806879e3becd7 schema:isbn 978-3-540-40671-6
72 978-3-540-45138-9
73 schema:name Mathematical Foundations of Computer Science 2003
74 rdf:type schema:Book
75 Need487b3386842bfb7eb96dbde19291f rdf:first Nf5376962ba4f423b9f6dea61ea3fdbd0
76 rdf:rest Na2d3ecf07c484f44a1f06c74f6898e85
77 Nf5376962ba4f423b9f6dea61ea3fdbd0 schema:familyName Rovan
78 schema:givenName Branislav
79 rdf:type schema:Person
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.011235103317.37 schema:affiliation grid-institutes:grid.412773.4
87 schema:familyName Kouno
88 schema:givenName Mitsuharu
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011235103317.37
90 rdf:type schema:Person
91 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
92 schema:familyName Chen
93 schema:givenName Zhi-Zhong
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
95 rdf:type schema:Person
96 grid-institutes:grid.412773.4 schema:alternateName Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-0394, Saitama, Japan
97 schema:name Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-0394, Saitama, Japan
98 rdf:type schema:Organization
 




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


...