On Even Triangulations of 2-Connected Embedded Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003-06-24

AUTHORS

Huaming Zhang , Xin He

ABSTRACT

Recently, Hoffmann and Kriegel proved an important combinatorial theorem 4: Every 2-connected bipartite plane graph G has a triangulation in which all vertices have even degree (it’s called an even triangulation). Combined with a classical Whitney’s Theorem, this result implies that every such a graph has a 3-colorable plane triangulation. Using this theorem, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. In 7, Zhang and He presented a linear time algorithm which relies on the complicated algebraic proof in 4. This proof cannot be extended to similar graphs embedded on high genus surfaces. It’s not known whether Hoffmann and Kriegel’s Theorem is true for such graphs.In this paper, we describe a totally independent and much simpler proof of the above theorem, using only graph-theoretic arguments. Our new proof can be easily extend to show the existence of even triangulations for similar graphs on high genus surfaces. Hence we show that Hoffmann and Kriegel’s theorem remains valid for such graphs. Our new proof leads to a very simple linear time algorithm for finding even triangulations. More... »

PAGES

139-148

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-40534-4
978-3-540-45071-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45071-8_16

DOI

http://dx.doi.org/10.1007/3-540-45071-8_16

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Amherst, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Amherst, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Huaming", 
        "id": "sg:person.012041227127.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Amherst, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Amherst, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-06-24", 
    "datePublishedReg": "2003-06-24", 
    "description": "Recently, Hoffmann and Kriegel proved an important combinatorial theorem 4: Every 2-connected bipartite plane graph G has a triangulation in which all vertices have even degree (it\u2019s called an even triangulation). Combined with a classical Whitney\u2019s Theorem, this result implies that every such a graph has a 3-colorable plane triangulation. Using this theorem, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. In 7, Zhang and He presented a linear time algorithm which relies on the complicated algebraic proof in 4. This proof cannot be extended to similar graphs embedded on high genus surfaces. It\u2019s not known whether Hoffmann and Kriegel\u2019s Theorem is true for such graphs.In this paper, we describe a totally independent and much simpler proof of the above theorem, using only graph-theoretic arguments. Our new proof can be easily extend to show the existence of even triangulations for similar graphs on high genus surfaces. Hence we show that Hoffmann and Kriegel\u2019s theorem remains valid for such graphs. Our new proof leads to a very simple linear time algorithm for finding even triangulations.", 
    "editor": [
      {
        "familyName": "Warnow", 
        "givenName": "Tandy", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhu", 
        "givenName": "Binhai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45071-8_16", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40534-4", 
        "978-3-540-45071-9"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "linear time algorithm", 
      "similar graphs", 
      "time algorithm", 
      "higher genus surfaces", 
      "such graphs", 
      "graph-theoretic arguments", 
      "graph", 
      "simple linear time algorithm", 
      "guard problem", 
      "algorithm", 
      "embedded graphs", 
      "triangulation", 
      "upper bounds", 
      "proof", 
      "graph G", 
      "art galleries", 
      "plane graph G", 
      "plane triangulations", 
      "simple proof", 
      "algebraic proof", 
      "vertices", 
      "bounds", 
      "theorem", 
      "new proof", 
      "galleries", 
      "Zhang", 
      "results", 
      "Kriegel", 
      "above theorem", 
      "degree", 
      "argument", 
      "existence", 
      "Theorem 4", 
      "surface", 
      "Hoffmann", 
      "problem", 
      "paper", 
      "Whitney's theorem", 
      "important combinatorial theorem 4", 
      "combinatorial theorem 4", 
      "bipartite plane graph G", 
      "classical Whitney\u2019s Theorem", 
      "prison guard problems", 
      "complicated algebraic proof", 
      "genus surfaces", 
      "Kriegel\u2019s Theorem", 
      "only graph-theoretic arguments", 
      "even triangulation"
    ], 
    "name": "On Even Triangulations of 2-Connected Embedded Graphs", 
    "pagination": "139-148", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042640174"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45071-8_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45071-8_16", 
      "https://app.dimensions.ai/details/publication/pub.1042640174"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:49", 
    "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/chapter/chapter_179.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45071-8_16"
  }
]
 

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/3-540-45071-8_16'

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/3-540-45071-8_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45071-8_16'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45071-8_16'


 

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

120 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45071-8_16 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N478bbc0e9b354ced9c13be78e2cf6a93
4 schema:datePublished 2003-06-24
5 schema:datePublishedReg 2003-06-24
6 schema:description Recently, Hoffmann and Kriegel proved an important combinatorial theorem 4: Every 2-connected bipartite plane graph G has a triangulation in which all vertices have even degree (it’s called an even triangulation). Combined with a classical Whitney’s Theorem, this result implies that every such a graph has a 3-colorable plane triangulation. Using this theorem, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. In 7, Zhang and He presented a linear time algorithm which relies on the complicated algebraic proof in 4. This proof cannot be extended to similar graphs embedded on high genus surfaces. It’s not known whether Hoffmann and Kriegel’s Theorem is true for such graphs.In this paper, we describe a totally independent and much simpler proof of the above theorem, using only graph-theoretic arguments. Our new proof can be easily extend to show the existence of even triangulations for similar graphs on high genus surfaces. Hence we show that Hoffmann and Kriegel’s theorem remains valid for such graphs. Our new proof leads to a very simple linear time algorithm for finding even triangulations.
7 schema:editor N37b146ff8cbb4e4295a329882e3e76e3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N4a60cec24daa471f910b589428dafda5
12 schema:keywords Hoffmann
13 Kriegel
14 Kriegel’s Theorem
15 Theorem 4
16 Whitney's theorem
17 Zhang
18 above theorem
19 algebraic proof
20 algorithm
21 argument
22 art galleries
23 bipartite plane graph G
24 bounds
25 classical Whitney’s Theorem
26 combinatorial theorem 4
27 complicated algebraic proof
28 degree
29 embedded graphs
30 even triangulation
31 existence
32 galleries
33 genus surfaces
34 graph
35 graph G
36 graph-theoretic arguments
37 guard problem
38 higher genus surfaces
39 important combinatorial theorem 4
40 linear time algorithm
41 new proof
42 only graph-theoretic arguments
43 paper
44 plane graph G
45 plane triangulations
46 prison guard problems
47 problem
48 proof
49 results
50 similar graphs
51 simple linear time algorithm
52 simple proof
53 such graphs
54 surface
55 theorem
56 time algorithm
57 triangulation
58 upper bounds
59 vertices
60 schema:name On Even Triangulations of 2-Connected Embedded Graphs
61 schema:pagination 139-148
62 schema:productId N668c65f1aeaa4cada2036df3defdb0c2
63 Ne82c66fdb38845049486935f8a04493b
64 schema:publisher Ncb10969b97e247dca78d376618930a0c
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042640174
66 https://doi.org/10.1007/3-540-45071-8_16
67 schema:sdDatePublished 2021-11-01T18:49
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N8ed4c54e3bc14ea0b8a57fc2bd764755
70 schema:url https://doi.org/10.1007/3-540-45071-8_16
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N0e3194eb6f4349eeacc4f761a1a9ef55 rdf:first Nc8379ddf1a2c4b598ae6c4e9a9047897
75 rdf:rest rdf:nil
76 N37b146ff8cbb4e4295a329882e3e76e3 rdf:first Nbcdd94671c8f47dabfd43b53485c3c24
77 rdf:rest N0e3194eb6f4349eeacc4f761a1a9ef55
78 N478bbc0e9b354ced9c13be78e2cf6a93 rdf:first sg:person.012041227127.88
79 rdf:rest Na8c8f3fd5d0d46faaf0a168027bedd1e
80 N4a60cec24daa471f910b589428dafda5 schema:isbn 978-3-540-40534-4
81 978-3-540-45071-9
82 schema:name Computing and Combinatorics
83 rdf:type schema:Book
84 N668c65f1aeaa4cada2036df3defdb0c2 schema:name dimensions_id
85 schema:value pub.1042640174
86 rdf:type schema:PropertyValue
87 N8ed4c54e3bc14ea0b8a57fc2bd764755 schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 Na8c8f3fd5d0d46faaf0a168027bedd1e rdf:first sg:person.011352641523.42
90 rdf:rest rdf:nil
91 Nbcdd94671c8f47dabfd43b53485c3c24 schema:familyName Warnow
92 schema:givenName Tandy
93 rdf:type schema:Person
94 Nc8379ddf1a2c4b598ae6c4e9a9047897 schema:familyName Zhu
95 schema:givenName Binhai
96 rdf:type schema:Person
97 Ncb10969b97e247dca78d376618930a0c schema:name Springer Nature
98 rdf:type schema:Organisation
99 Ne82c66fdb38845049486935f8a04493b schema:name doi
100 schema:value 10.1007/3-540-45071-8_16
101 rdf:type schema:PropertyValue
102 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
103 schema:name Mathematical Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
106 schema:name Pure Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
109 schema:familyName He
110 schema:givenName Xin
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
112 rdf:type schema:Person
113 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.273335.3
114 schema:familyName Zhang
115 schema:givenName Huaming
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
117 rdf:type schema:Person
118 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Amherst, NY, USA
119 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Amherst, NY, USA
120 rdf:type schema:Organization
 




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


...