Computing the Girth of a Planar Graph in Linear Time View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Hsien-Chih Chang , Hsueh-I Lu

ABSTRACT

The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an n-node unweighted undirected planar graph. The first non-trivial algorithm for the problem, given by Djidjev, runs in O(n5/4logn) time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to O(nlog2n). Weimann and Yuster further reduced the running time to O(nlogn). In this paper, we solve the problem in O(n) time. More... »

PAGES

225-236

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22685-4_20

DOI

http://dx.doi.org/10.1007/978-3-642-22685-4_20

DIMENSIONS

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


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 Computer Science and Information Engineering, National Taiwan University, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "Hsien-Chih", 
        "id": "sg:person.012371633015.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012371633015.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an n-node unweighted undirected planar graph. The first non-trivial algorithm for the problem, given by Djidjev, runs in O(n5/4logn) time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to O(nlog2n). Weimann and Yuster further reduced the running time to O(nlogn). In this paper, we solve the problem in O(n) time.", 
    "editor": [
      {
        "familyName": "Fu", 
        "givenName": "Bin", 
        "type": "Person"
      }, 
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22685-4_20", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22684-7", 
        "978-3-642-22685-4"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "planar graphs", 
      "first non-trivial algorithm", 
      "undirected planar graphs", 
      "non-trivial algorithm", 
      "linear time", 
      "graph", 
      "minimum weight", 
      "simple cycle", 
      "problem", 
      "Fakcharoenphol", 
      "Yuster", 
      "algorithm", 
      "nodes", 
      "Nanongkai", 
      "girth", 
      "time", 
      "Weimann", 
      "weight", 
      "cycle", 
      "paper"
    ], 
    "name": "Computing the Girth of a Planar Graph in Linear Time", 
    "pagination": "225-236", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016256202"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22685-4_20"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22685-4_20", 
      "https://app.dimensions.ai/details/publication/pub.1016256202"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10: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/chapter/chapter_68.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22685-4_20"
  }
]
 

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-642-22685-4_20'

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-642-22685-4_20'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22685-4_20'

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-642-22685-4_20'


 

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

92 TRIPLES      23 PREDICATES      46 URIs      39 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22685-4_20 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nbb08d55e0c7b4226bcd33336fa924aa8
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an n-node unweighted undirected planar graph. The first non-trivial algorithm for the problem, given by Djidjev, runs in O(n5/4logn) time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to O(nlog2n). Weimann and Yuster further reduced the running time to O(nlogn). In this paper, we solve the problem in O(n) time.
7 schema:editor N5ac78af69df645e3b006a65a6a9d3553
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nccc2b0aa38ab4577a7de0197def77d0e
12 schema:keywords Fakcharoenphol
13 Nanongkai
14 Weimann
15 Yuster
16 algorithm
17 cycle
18 first non-trivial algorithm
19 girth
20 graph
21 linear time
22 minimum weight
23 nodes
24 non-trivial algorithm
25 paper
26 planar graphs
27 problem
28 simple cycle
29 time
30 undirected planar graphs
31 weight
32 schema:name Computing the Girth of a Planar Graph in Linear Time
33 schema:pagination 225-236
34 schema:productId N1a31ebd00be14957ba6e9595e567ff6e
35 Nf32cfe09d906404f8b8cbf56e4e3ac2a
36 schema:publisher N6987b3dacfb54a60b57387e433e46e08
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016256202
38 https://doi.org/10.1007/978-3-642-22685-4_20
39 schema:sdDatePublished 2022-05-10T10:55
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher N0f0f1763e8d145628b96ce204516a3c8
42 schema:url https://doi.org/10.1007/978-3-642-22685-4_20
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N0f0f1763e8d145628b96ce204516a3c8 schema:name Springer Nature - SN SciGraph project
47 rdf:type schema:Organization
48 N1a31ebd00be14957ba6e9595e567ff6e schema:name dimensions_id
49 schema:value pub.1016256202
50 rdf:type schema:PropertyValue
51 N28475bf1c3ad487fb8bfb773ef630306 schema:familyName Fu
52 schema:givenName Bin
53 rdf:type schema:Person
54 N4d96ad00d4f641dda6b8adb329b9c2e1 schema:familyName Du
55 schema:givenName Ding-Zhu
56 rdf:type schema:Person
57 N5ac78af69df645e3b006a65a6a9d3553 rdf:first N28475bf1c3ad487fb8bfb773ef630306
58 rdf:rest N73e0d82e5fc645b9973f56de5186c9cd
59 N6987b3dacfb54a60b57387e433e46e08 schema:name Springer Nature
60 rdf:type schema:Organisation
61 N73e0d82e5fc645b9973f56de5186c9cd rdf:first N4d96ad00d4f641dda6b8adb329b9c2e1
62 rdf:rest rdf:nil
63 N9f6108528ac04df1a8142b4684d39c41 rdf:first sg:person.013345515575.46
64 rdf:rest rdf:nil
65 Nbb08d55e0c7b4226bcd33336fa924aa8 rdf:first sg:person.012371633015.50
66 rdf:rest N9f6108528ac04df1a8142b4684d39c41
67 Nccc2b0aa38ab4577a7de0197def77d0e schema:isbn 978-3-642-22684-7
68 978-3-642-22685-4
69 schema:name Computing and Combinatorics
70 rdf:type schema:Book
71 Nf32cfe09d906404f8b8cbf56e4e3ac2a schema:name doi
72 schema:value 10.1007/978-3-642-22685-4_20
73 rdf:type schema:PropertyValue
74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information and Computing Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
78 schema:name Computation Theory and Mathematics
79 rdf:type schema:DefinedTerm
80 sg:person.012371633015.50 schema:affiliation grid-institutes:grid.19188.39
81 schema:familyName Chang
82 schema:givenName Hsien-Chih
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012371633015.50
84 rdf:type schema:Person
85 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
86 schema:familyName Lu
87 schema:givenName Hsueh-I
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
89 rdf:type schema:Person
90 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University, Taiwan
91 schema:name Department of Computer Science and Information Engineering, National Taiwan University, Taiwan
92 rdf:type schema:Organization
 




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


...