# Probe Ptolemaic Graphs

Ontology type: schema:Chapter

### Chapter Info

DATE

2008-01-01

AUTHORS ABSTRACT

Given a class of graphs, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document}, a graph G is a probe graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document} if its vertices can be partitioned into two sets, ℙ (the probes) and ℕ (the nonprobes), where ℕ is an independent set, such that G can be embedded into a graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document} by adding edges between certain nonprobes. In this paper we study the probe graphs of ptolemaic graphs when the partition of vertices is unknown. We present some characterizations of probe ptolemaic graphs and show that there exists a polynomial-time recognition algorithm for probe ptolemaic graphs. More... »

PAGES

468-477

### Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-69732-9
978-3-540-69733-6

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-69733-6_46

DOI

http://dx.doi.org/10.1007/978-3-540-69733-6_46

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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, University of Delaware Newark, 19716, Delaware, USA",
"id": "http://www.grid.ac/institutes/grid.33489.35",
"name": [
"Department of Mathematical Sciences, University of Delaware Newark, 19716, Delaware, USA"
],
"type": "Organization"
},
"familyName": "Chandler",
"givenName": "David B.",
"id": "sg:person.015431467001.58",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015431467001.58"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"Department of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan"
],
"type": "Organization"
},
"familyName": "Chang",
"givenName": "Maw-Shang",
"id": "sg:person.013174232477.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematical Sciences, University of Delaware Newark, 19716, Delaware, USA",
"id": "http://www.grid.ac/institutes/grid.33489.35",
"name": [
"Department of Mathematical Sciences, University of Delaware Newark, 19716, Delaware, USA"
],
"type": "Organization"
},
"familyName": "Kloks",
"givenName": "Ton",
"id": "sg:person.011052721431.97",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052721431.97"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t Rostock, 18051, Rostock, Germany",
"id": "http://www.grid.ac/institutes/grid.10493.3f",
"name": [
"Institut f\u00fcr Informatik, Universit\u00e4t Rostock, 18051, Rostock, Germany"
],
"type": "Organization"
},
"familyName": "Le",
"givenName": "Van Bang",
"id": "sg:person.07725346237.01",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07725346237.01"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Hualien, Taiwan",
"id": "http://www.grid.ac/institutes/grid.260567.0",
"name": [
"Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Hualien, Taiwan"
],
"type": "Organization"
},
"familyName": "Peng",
"givenName": "Sheng-Lung",
"id": "sg:person.013531324035.31",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31"
],
"type": "Person"
}
],
"datePublished": "2008-01-01",
"datePublishedReg": "2008-01-01",
"description": "Given a class of graphs, \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{G}$\\end{document}, a graph G is a probe graph of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{G}$\\end{document} if its vertices can be partitioned into two sets, \u2119 (the probes) and \u2115 (the nonprobes), where \u2115 is an independent set, such that G can be embedded into a graph of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{G}$\\end{document} by adding edges between certain nonprobes. In this paper we study the probe graphs of ptolemaic graphs when the partition of vertices is unknown. We present some characterizations of probe ptolemaic graphs and show that there exists a polynomial-time recognition algorithm for probe ptolemaic graphs.",
"editor": [
{
"familyName": "Hu",
"givenName": "Xiaodong",
"type": "Person"
},
{
"familyName": "Wang",
"givenName": "Jie",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-69733-6_46",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-69732-9",
"978-3-540-69733-6"
],
"name": "Computing and Combinatorics",
"type": "Book"
},
"keywords": [
"probe graphs",
"certain nonprobes",
"partition of vertices",
"polynomial-time recognition algorithm",
"recognition algorithm",
"ptolemaic graphs",
"graph",
"class of graphs",
"independent set",
"set",
"algorithm",
"vertices",
"nonprobes",
"graph G",
"partition",
"edge",
"class",
"characterization",
"paper",
"probe ptolemaic graphs"
],
"name": "Probe Ptolemaic Graphs",
"pagination": "468-477",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1043529202"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-69733-6_46"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-69733-6_46",
"https://app.dimensions.ai/details/publication/pub.1043529202"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:52",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_243.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-69733-6_46"
}
]

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-69733-6_46'

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-69733-6_46'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-69733-6_46'

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-69733-6_46'

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

122 TRIPLES      23 PREDICATES      45 URIs      38 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author Ncc751a402c7248988a6cca73edb95a06
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description Given a class of graphs, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document}, a graph G is a probe graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document} if its vertices can be partitioned into two sets, ℙ (the probes) and ℕ (the nonprobes), where ℕ is an independent set, such that G can be embedded into a graph of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{G}$\end{document} by adding edges between certain nonprobes. In this paper we study the probe graphs of ptolemaic graphs when the partition of vertices is unknown. We present some characterizations of probe ptolemaic graphs and show that there exists a polynomial-time recognition algorithm for probe ptolemaic graphs.
7 schema:editor N5d94d2a684ca475fa0c537da35151ba0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
12 schema:keywords algorithm
13 certain nonprobes
14 characterization
15 class
16 class of graphs
17 edge
18 graph
19 graph G
20 independent set
21 nonprobes
22 paper
23 partition
24 partition of vertices
25 polynomial-time recognition algorithm
26 probe graphs
27 probe ptolemaic graphs
28 ptolemaic graphs
29 recognition algorithm
30 set
31 vertices
32 schema:name Probe Ptolemaic Graphs
33 schema:pagination 468-477
34 schema:productId N5243e53ef4da4d19abd82c66b8cc0ec0
35 Na55594efdf304351b6218954d8092b4a
36 schema:publisher N1d613359591244b590eca7592ff48b69
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043529202
38 https://doi.org/10.1007/978-3-540-69733-6_46
39 schema:sdDatePublished 2021-11-01T18:52
41 schema:sdPublisher N89d08840777443f6b17692a9e55b2c9a
42 schema:url https://doi.org/10.1007/978-3-540-69733-6_46
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N1d613359591244b590eca7592ff48b69 schema:name Springer Nature
47 rdf:type schema:Organisation
48 N2323c414d7684ba383e9d10dd6dc364c rdf:first sg:person.011052721431.97
49 rdf:rest Ned3ed3f9bc114fea98b4d96dccc0304e
50 N2d3a74f5917042668da57533acc257e6 rdf:first N80a455d753de478e9dc90ee1c4edb070
51 rdf:rest rdf:nil
52 N5243e53ef4da4d19abd82c66b8cc0ec0 schema:name dimensions_id
53 schema:value pub.1043529202
54 rdf:type schema:PropertyValue
55 N5d94d2a684ca475fa0c537da35151ba0 rdf:first Nfb3c5a5251164f1f9ccb34cb27a0d1ee
56 rdf:rest N2d3a74f5917042668da57533acc257e6
57 N80a455d753de478e9dc90ee1c4edb070 schema:familyName Wang
58 schema:givenName Jie
59 rdf:type schema:Person
60 N847a0c5747f74b679973859d606e3a6c rdf:first sg:person.013531324035.31
61 rdf:rest rdf:nil
62 N89d08840777443f6b17692a9e55b2c9a schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N93492eb8c5db40ee814f2287b904758e rdf:first sg:person.013174232477.45
65 rdf:rest N2323c414d7684ba383e9d10dd6dc364c
66 Na55594efdf304351b6218954d8092b4a schema:name doi
67 schema:value 10.1007/978-3-540-69733-6_46
68 rdf:type schema:PropertyValue
69 Ncc751a402c7248988a6cca73edb95a06 rdf:first sg:person.015431467001.58
70 rdf:rest N93492eb8c5db40ee814f2287b904758e
72 978-3-540-69733-6
73 schema:name Computing and Combinatorics
74 rdf:type schema:Book
75 Ned3ed3f9bc114fea98b4d96dccc0304e rdf:first sg:person.07725346237.01
76 rdf:rest N847a0c5747f74b679973859d606e3a6c
77 Nfb3c5a5251164f1f9ccb34cb27a0d1ee schema:familyName Hu
78 schema:givenName Xiaodong
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.011052721431.97 schema:affiliation grid-institutes:grid.33489.35
87 schema:familyName Kloks
88 schema:givenName Ton
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052721431.97
90 rdf:type schema:Person
91 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
92 schema:familyName Chang
93 schema:givenName Maw-Shang
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
95 rdf:type schema:Person
96 sg:person.013531324035.31 schema:affiliation grid-institutes:grid.260567.0
97 schema:familyName Peng
98 schema:givenName Sheng-Lung
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
100 rdf:type schema:Person
101 sg:person.015431467001.58 schema:affiliation grid-institutes:grid.33489.35
102 schema:familyName Chandler
103 schema:givenName David B.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015431467001.58
105 rdf:type schema:Person
106 sg:person.07725346237.01 schema:affiliation grid-institutes:grid.10493.3f
107 schema:familyName Le
108 schema:givenName Van Bang
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07725346237.01
110 rdf:type schema:Person
111 grid-institutes:grid.10493.3f schema:alternateName Institut für Informatik, Universität Rostock, 18051, Rostock, Germany
112 schema:name Institut für Informatik, Universität Rostock, 18051, Rostock, Germany
113 rdf:type schema:Organization
114 grid-institutes:grid.260567.0 schema:alternateName Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Hualien, Taiwan
115 schema:name Department of Computer Science and Information Engineering, National Dong Hwa University, 97401, Hualien, Taiwan
116 rdf:type schema:Organization
117 grid-institutes:grid.33489.35 schema:alternateName Department of Mathematical Sciences, University of Delaware Newark, 19716, Delaware, USA
118 schema:name Department of Mathematical Sciences, University of Delaware Newark, 19716, Delaware, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan
121 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan
122 rdf:type schema:Organization