Graphs that Are Not Pairwise Compatible: A New Proof Technique (Extended Abstract) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018

AUTHORS

Pierluigi Baiocchi , Tiziana Calamoneri , Angelo Monti , Rossella Petreschi

ABSTRACT

A graph \(G=(V,E)\) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers \(d_{min}\) and \(d_{max}\), \(d_{min} \le d_{max}\), such that each node \(u \in V\) is uniquely associated to a leaf of T and there is an edge \((u,v) \in E\) if and only if \(d_{min} \le d_{T} (u, v) \le d_{max}\), where \(d_{T} (u, v)\) is the sum of the weights of the edges on the unique path \(P_{T}(u,v)\) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. Despite numerous efforts, a complete characterization of the PCG class is not known yet. In this paper we propose a new proof technique that allows us to show that some interesting classes of graphs have empty intersection with PCG. We demonstrate our technique by showing many graph classes that do not lie in PCG. As a side effect, we show a not pairwise compatibility planar graph with 8 nodes (i.e. \(C^2_8\)), so improving the previously known result concerning the smallest planar graph known not to be PCG. More... »

PAGES

39-51

References to SciGraph publications

Book

TITLE

Combinatorial Algorithms

ISBN

978-3-319-94666-5
978-3-319-94667-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-94667-2_4

DOI

http://dx.doi.org/10.1007/978-3-319-94667-2_4

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Sapienza\u201d University of Rome"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Baiocchi", 
        "givenName": "Pierluigi", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Sapienza\u201d University of Rome"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Calamoneri", 
        "givenName": "Tiziana", 
        "id": "sg:person.013577775161.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Sapienza\u201d University of Rome"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Monti", 
        "givenName": "Angelo", 
        "id": "sg:person.013471123531.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Sapienza\u201d University of Rome"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Petreschi", 
        "givenName": "Rossella", 
        "id": "sg:person.011402427702.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-39763-2_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001248165", 
          "https://doi.org/10.1007/978-3-540-39763-2_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39763-2_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001248165", 
          "https://doi.org/10.1007/978-3-540-39763-2_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-78773-0_42", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017112248", 
          "https://doi.org/10.1007/978-3-540-78773-0_42"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-78773-0_42", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017112248", 
          "https://doi.org/10.1007/978-3-540-78773-0_42"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2013.12.015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021066806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2015.01.011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028311851"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2015.01.011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028311851"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s12190-008-0204-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028947261", 
          "https://doi.org/10.1007/s12190-008-0204-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/comjnl/bxs087", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059480409"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/comjnl/bxt068", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059480552"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/140978053", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062872538"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s1793830910000917", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063025166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2412923", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069921277"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.7155/jgaa.00286", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1073626572"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.7155/jgaa.00419", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084671473"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/iciev.2013.6572681", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093235126"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018", 
    "datePublishedReg": "2018-01-01", 
    "description": "A graph \\(G=(V,E)\\) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers \\(d_{min}\\) and \\(d_{max}\\), \\(d_{min} \\le d_{max}\\), such that each node \\(u \\in V\\) is uniquely associated to a leaf of T and there is an edge \\((u,v) \\in E\\) if and only if \\(d_{min} \\le d_{T} (u, v) \\le d_{max}\\), where \\(d_{T} (u, v)\\) is the sum of the weights of the edges on the unique path \\(P_{T}(u,v)\\) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. Despite numerous efforts, a complete characterization of the PCG class is not known yet. In this paper we propose a new proof technique that allows us to show that some interesting classes of graphs have empty intersection with PCG. We demonstrate our technique by showing many graph classes that do not lie in PCG. As a side effect, we show a not pairwise compatibility planar graph with 8 nodes (i.e. \\(C^2_8\\)), so improving the previously known result concerning the smallest planar graph known not to be PCG.", 
    "editor": [
      {
        "familyName": "Iliopoulos", 
        "givenName": "Costas", 
        "type": "Person"
      }, 
      {
        "familyName": "Leong", 
        "givenName": "Hon Wai", 
        "type": "Person"
      }, 
      {
        "familyName": "Sung", 
        "givenName": "Wing-Kin", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-94667-2_4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-94666-5", 
        "978-3-319-94667-2"
      ], 
      "name": "Combinatorial Algorithms", 
      "type": "Book"
    }, 
    "name": "Graphs that Are Not Pairwise Compatible: A New Proof Technique (Extended Abstract)", 
    "pagination": "39-51", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-94667-2_4"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "834a787b83904accd03fd871c58a6f89f472c6cae4a946641d052eca043e84a8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1105295650"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-94667-2_4", 
      "https://app.dimensions.ai/details/publication/pub.1105295650"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:32", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8697_00000604.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-94667-2_4"
  }
]
 

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-319-94667-2_4'

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-319-94667-2_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-94667-2_4'

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-319-94667-2_4'


 

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

137 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-94667-2_4 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N024e598871c847fda9e305c51a303c57
4 schema:citation sg:pub.10.1007/978-3-540-39763-2_14
5 sg:pub.10.1007/978-3-540-78773-0_42
6 sg:pub.10.1007/s12190-008-0204-7
7 https://doi.org/10.1016/j.tcs.2013.12.015
8 https://doi.org/10.1016/j.tcs.2015.01.011
9 https://doi.org/10.1093/comjnl/bxs087
10 https://doi.org/10.1093/comjnl/bxt068
11 https://doi.org/10.1109/iciev.2013.6572681
12 https://doi.org/10.1137/140978053
13 https://doi.org/10.1142/s1793830910000917
14 https://doi.org/10.2307/2412923
15 https://doi.org/10.7155/jgaa.00286
16 https://doi.org/10.7155/jgaa.00419
17 schema:datePublished 2018
18 schema:datePublishedReg 2018-01-01
19 schema:description A graph \(G=(V,E)\) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers \(d_{min}\) and \(d_{max}\), \(d_{min} \le d_{max}\), such that each node \(u \in V\) is uniquely associated to a leaf of T and there is an edge \((u,v) \in E\) if and only if \(d_{min} \le d_{T} (u, v) \le d_{max}\), where \(d_{T} (u, v)\) is the sum of the weights of the edges on the unique path \(P_{T}(u,v)\) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. Despite numerous efforts, a complete characterization of the PCG class is not known yet. In this paper we propose a new proof technique that allows us to show that some interesting classes of graphs have empty intersection with PCG. We demonstrate our technique by showing many graph classes that do not lie in PCG. As a side effect, we show a not pairwise compatibility planar graph with 8 nodes (i.e. \(C^2_8\)), so improving the previously known result concerning the smallest planar graph known not to be PCG.
20 schema:editor Nbf1402741ced455d812ef753fff07fe5
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree false
24 schema:isPartOf Nd95dd06e54c54d6ebd6a8440ea593098
25 schema:name Graphs that Are Not Pairwise Compatible: A New Proof Technique (Extended Abstract)
26 schema:pagination 39-51
27 schema:productId N18b64ae618d64698be7d0633f6cc08a5
28 N3f9d8e9ff1374cb29322d46c1ee3f11b
29 Nb7a980a4eb674ea4941df832a120d00b
30 schema:publisher N373ec340f68e45f5bec1f14597736c6e
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105295650
32 https://doi.org/10.1007/978-3-319-94667-2_4
33 schema:sdDatePublished 2019-04-16T00:32
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N8c8c34a58ba14ee1b3e9265c8d060b5a
36 schema:url http://link.springer.com/10.1007/978-3-319-94667-2_4
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N024e598871c847fda9e305c51a303c57 rdf:first N231d01fd518d4fb08ba0ef95b4a10b82
41 rdf:rest N6c92676ea9904484909fe1fe1147d928
42 N0a58ecedb79040079dde979774614619 rdf:first sg:person.013471123531.02
43 rdf:rest N634635c35a9f4742bff5bf6bac18db18
44 N18b64ae618d64698be7d0633f6cc08a5 schema:name readcube_id
45 schema:value 834a787b83904accd03fd871c58a6f89f472c6cae4a946641d052eca043e84a8
46 rdf:type schema:PropertyValue
47 N231d01fd518d4fb08ba0ef95b4a10b82 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
48 schema:familyName Baiocchi
49 schema:givenName Pierluigi
50 rdf:type schema:Person
51 N2744bb959f8d4ae1b1c005742ad535f6 schema:familyName Leong
52 schema:givenName Hon Wai
53 rdf:type schema:Person
54 N373ec340f68e45f5bec1f14597736c6e schema:location Cham
55 schema:name Springer International Publishing
56 rdf:type schema:Organisation
57 N3f9d8e9ff1374cb29322d46c1ee3f11b schema:name dimensions_id
58 schema:value pub.1105295650
59 rdf:type schema:PropertyValue
60 N634635c35a9f4742bff5bf6bac18db18 rdf:first sg:person.011402427702.78
61 rdf:rest rdf:nil
62 N6c92676ea9904484909fe1fe1147d928 rdf:first sg:person.013577775161.22
63 rdf:rest N0a58ecedb79040079dde979774614619
64 N6d7085a7fd214baa8530fd27a9134f48 schema:familyName Iliopoulos
65 schema:givenName Costas
66 rdf:type schema:Person
67 N8c8c34a58ba14ee1b3e9265c8d060b5a schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N94eee2d7386a41f187046b81cc731c4d schema:familyName Sung
70 schema:givenName Wing-Kin
71 rdf:type schema:Person
72 Nb4592cbdf5354022a7441d36921636f1 rdf:first N2744bb959f8d4ae1b1c005742ad535f6
73 rdf:rest Nc94b271e03524be7aa698dfdcb4dbf49
74 Nb7a980a4eb674ea4941df832a120d00b schema:name doi
75 schema:value 10.1007/978-3-319-94667-2_4
76 rdf:type schema:PropertyValue
77 Nbf1402741ced455d812ef753fff07fe5 rdf:first N6d7085a7fd214baa8530fd27a9134f48
78 rdf:rest Nb4592cbdf5354022a7441d36921636f1
79 Nc94b271e03524be7aa698dfdcb4dbf49 rdf:first N94eee2d7386a41f187046b81cc731c4d
80 rdf:rest rdf:nil
81 Nd95dd06e54c54d6ebd6a8440ea593098 schema:isbn 978-3-319-94666-5
82 978-3-319-94667-2
83 schema:name Combinatorial Algorithms
84 rdf:type schema:Book
85 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
86 schema:name Mathematical Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
89 schema:name Pure Mathematics
90 rdf:type schema:DefinedTerm
91 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
92 schema:familyName Petreschi
93 schema:givenName Rossella
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
95 rdf:type schema:Person
96 sg:person.013471123531.02 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
97 schema:familyName Monti
98 schema:givenName Angelo
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02
100 rdf:type schema:Person
101 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
102 schema:familyName Calamoneri
103 schema:givenName Tiziana
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
105 rdf:type schema:Person
106 sg:pub.10.1007/978-3-540-39763-2_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001248165
107 https://doi.org/10.1007/978-3-540-39763-2_14
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-540-78773-0_42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017112248
110 https://doi.org/10.1007/978-3-540-78773-0_42
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/s12190-008-0204-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028947261
113 https://doi.org/10.1007/s12190-008-0204-7
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/j.tcs.2013.12.015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021066806
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/j.tcs.2015.01.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028311851
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1093/comjnl/bxs087 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059480409
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1093/comjnl/bxt068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059480552
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1109/iciev.2013.6572681 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093235126
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1137/140978053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062872538
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1142/s1793830910000917 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063025166
128 rdf:type schema:CreativeWork
129 https://doi.org/10.2307/2412923 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069921277
130 rdf:type schema:CreativeWork
131 https://doi.org/10.7155/jgaa.00286 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073626572
132 rdf:type schema:CreativeWork
133 https://doi.org/10.7155/jgaa.00419 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084671473
134 rdf:type schema:CreativeWork
135 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
136 schema:name Sapienza” University of Rome
137 rdf:type schema:Organization
 




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


...