Recognizing Map Graphs of Bounded Treewidth Article Swipe

PDF

Patrizio Angelini , Michael A. Bekos , Giordano Da Lozzo , Martin Gronemann , Fabrizio Montecchiani , Alessandra Tappini ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.1007/s00453-023-01180-6

A map is a partition of the sphere into interior-disjoint regions homeomorphic to closed disks. Some regions are labeled as nations, while the remaining ones are labeled as holes. A map in which at most k nations touch at the same point is a k -map, while it is hole-free if it contains no holes. A graph is a map graph if there is a bijection between its vertices and the nations of a map, such that two nations touch if and only the corresponding vertices are connected by an edge. We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph. It reports a certificate in the form of a so-called witness, if the input is a yes-instance. Our algorithmic framework is general enough to test, for any k , if the input graph admits a k -map or a hole-free k -map.

Related Topics

Mathematical Analysis

Geometry

Concepts

Combinatorics Treewidth Bijection Mathematics Discrete mathematics Parameterized complexity Planar graph Antipodal point Partial k-tree Bounded function 1-planar graph Graph Pathwidth Chordal graph Line graph Mathematical analysis Geometry

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1007/s00453-023-01180-6
PDF: https://link.springer.com/content/pdf/10.1007/s00453-023-01180-6.pdf
OA Status: hybrid
Cited By: 1
References: 34
Related Works: 10
OpenAlex ID: https://openalex.org/W4388188757

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4388188757

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1007/s00453-023-01180-6

Digital Object Identifier
Title: Recognizing Map Graphs of Bounded Treewidth

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-10-27

Full publication date if available
Authors: Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, Alessandra Tappini

List of authors in order
Landing page: https://doi.org/10.1007/s00453-023-01180-6

Publisher landing page
PDF URL: https://link.springer.com/content/pdf/10.1007/s00453-023-01180-6.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: hybrid

Open access status per OpenAlex
OA URL: https://link.springer.com/content/pdf/10.1007/s00453-023-01180-6.pdf

Direct OA link when available
Concepts: Combinatorics, Treewidth, Bijection, Mathematics, Discrete mathematics, Parameterized complexity, Planar graph, Antipodal point, Partial k-tree, Bounded function, 1-planar graph, Graph, Pathwidth, Chordal graph, Line graph, Mathematical analysis, Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2023: 1

Per-year citation counts (last 5 years)
References (count): 34

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4388188757
doi	https://doi.org/10.1007/s00453-023-01180-6
ids.doi	https://doi.org/10.1007/s00453-023-01180-6
ids.openalex	https://openalex.org/W4388188757
fwci	0.3089612
type	article
title	Recognizing Map Graphs of Bounded Treewidth
biblio.issue	2
biblio.volume	86
biblio.last_page	637
biblio.first_page	613
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	1.0
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T12541
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9993000030517578
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Graph Labeling and Dimension Problems
topics[2].id	https://openalex.org/T10720
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.996399998664856
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Complexity and Algorithms in Graphs
funders[0].id	https://openalex.org/F4320326523
funders[0].ror	https://ror.org/00x27da85
funders[0].display_name	Università degli Studi di Perugia
is_xpac	False
apc_list.value	2290
apc_list.currency	EUR
apc_list.value_usd	2890
apc_paid.value	2290
apc_paid.currency	EUR
apc_paid.value_usd	2890
concepts[0].id	https://openalex.org/C114614502
concepts[0].level	1
concepts[0].score	0.787390947341919
concepts[0].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[0].display_name	Combinatorics
concepts[1].id	https://openalex.org/C132569581
concepts[1].level	5
concepts[1].score	0.6415297985076904
concepts[1].wikidata	https://www.wikidata.org/wiki/Q5067368
concepts[1].display_name	Treewidth
concepts[2].id	https://openalex.org/C24424167
concepts[2].level	2
concepts[2].score	0.6067198514938354
concepts[2].wikidata	https://www.wikidata.org/wiki/Q180907
concepts[2].display_name	Bijection
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.5787941813468933
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C118615104
concepts[4].level	1
concepts[4].score	0.5154746174812317
concepts[4].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[4].display_name	Discrete mathematics
concepts[5].id	https://openalex.org/C165464430
concepts[5].level	2
concepts[5].score	0.46824681758880615
concepts[5].wikidata	https://www.wikidata.org/wiki/Q1570441
concepts[5].display_name	Parameterized complexity
concepts[6].id	https://openalex.org/C101837359
concepts[6].level	3
concepts[6].score	0.46798133850097656
concepts[6].wikidata	https://www.wikidata.org/wiki/Q547823
concepts[6].display_name	Planar graph
concepts[7].id	https://openalex.org/C70943382
concepts[7].level	2
concepts[7].score	0.43174445629119873
concepts[7].wikidata	https://www.wikidata.org/wiki/Q505356
concepts[7].display_name	Antipodal point
concepts[8].id	https://openalex.org/C128764233
concepts[8].level	5
concepts[8].score	0.42375144362449646
concepts[8].wikidata	https://www.wikidata.org/wiki/Q7140374
concepts[8].display_name	Partial k-tree
concepts[9].id	https://openalex.org/C34388435
concepts[9].level	2
concepts[9].score	0.41265636682510376
concepts[9].wikidata	https://www.wikidata.org/wiki/Q2267362
concepts[9].display_name	Bounded function
concepts[10].id	https://openalex.org/C102192266
concepts[10].level	4
concepts[10].score	0.37889260053634644
concepts[10].wikidata	https://www.wikidata.org/wiki/Q4545823
concepts[10].display_name	1-planar graph
concepts[11].id	https://openalex.org/C132525143
concepts[11].level	2
concepts[11].score	0.36930686235427856
concepts[11].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[11].display_name	Graph
concepts[12].id	https://openalex.org/C43517604
concepts[12].level	4
concepts[12].score	0.29753512144088745
concepts[12].wikidata	https://www.wikidata.org/wiki/Q7144893
concepts[12].display_name	Pathwidth
concepts[13].id	https://openalex.org/C160446614
concepts[13].level	3
concepts[13].score	0.28386765718460083
concepts[13].wikidata	https://www.wikidata.org/wiki/Q1322892
concepts[13].display_name	Chordal graph
concepts[14].id	https://openalex.org/C203776342
concepts[14].level	3
concepts[14].score	0.198953777551651
concepts[14].wikidata	https://www.wikidata.org/wiki/Q1378376
concepts[14].display_name	Line graph
concepts[15].id	https://openalex.org/C134306372
concepts[15].level	1
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[15].display_name	Mathematical analysis
concepts[16].id	https://openalex.org/C2524010
concepts[16].level	1
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[16].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/combinatorics
keywords[0].score	0.787390947341919
keywords[0].display_name	Combinatorics
keywords[1].id	https://openalex.org/keywords/treewidth
keywords[1].score	0.6415297985076904
keywords[1].display_name	Treewidth
keywords[2].id	https://openalex.org/keywords/bijection
keywords[2].score	0.6067198514938354
keywords[2].display_name	Bijection
keywords[3].id	https://openalex.org/keywords/mathematics
keywords[3].score	0.5787941813468933
keywords[3].display_name	Mathematics
keywords[4].id	https://openalex.org/keywords/discrete-mathematics
keywords[4].score	0.5154746174812317
keywords[4].display_name	Discrete mathematics
keywords[5].id	https://openalex.org/keywords/parameterized-complexity
keywords[5].score	0.46824681758880615
keywords[5].display_name	Parameterized complexity
keywords[6].id	https://openalex.org/keywords/planar-graph
keywords[6].score	0.46798133850097656
keywords[6].display_name	Planar graph
keywords[7].id	https://openalex.org/keywords/antipodal-point
keywords[7].score	0.43174445629119873
keywords[7].display_name	Antipodal point
keywords[8].id	https://openalex.org/keywords/partial-k-tree
keywords[8].score	0.42375144362449646
keywords[8].display_name	Partial k-tree
keywords[9].id	https://openalex.org/keywords/bounded-function
keywords[9].score	0.41265636682510376
keywords[9].display_name	Bounded function
keywords[10].id	https://openalex.org/keywords/1-planar-graph
keywords[10].score	0.37889260053634644
keywords[10].display_name	1-planar graph
keywords[11].id	https://openalex.org/keywords/graph
keywords[11].score	0.36930686235427856
keywords[11].display_name	Graph
keywords[12].id	https://openalex.org/keywords/pathwidth
keywords[12].score	0.29753512144088745
keywords[12].display_name	Pathwidth
keywords[13].id	https://openalex.org/keywords/chordal-graph
keywords[13].score	0.28386765718460083
keywords[13].display_name	Chordal graph
keywords[14].id	https://openalex.org/keywords/line-graph
keywords[14].score	0.198953777551651
keywords[14].display_name	Line graph
language	en
locations[0].id	doi:10.1007/s00453-023-01180-6
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S89324355
locations[0].source.issn	0178-4617, 1432-0541
locations[0].source.type	journal
locations[0].source.is_oa	False
locations[0].source.issn_l	0178-4617
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Algorithmica
locations[0].source.host_organization	https://openalex.org/P4310319900
locations[0].source.host_organization_name	Springer Science+Business Media
locations[0].source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
locations[0].source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
locations[0].license	cc-by
locations[0].pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-023-01180-6.pdf
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Algorithmica
locations[0].landing_page_url	https://doi.org/10.1007/s00453-023-01180-6
locations[1].id	pmh:oai:iris.uniroma3.it:11590/469307
locations[1].is_oa	False
locations[1].source.id	https://openalex.org/S4377196120
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	Iris (Roma Tre University)
locations[1].source.host_organization	https://openalex.org/I119003972
locations[1].source.host_organization_name	Roma Tre University
locations[1].source.host_organization_lineage	https://openalex.org/I119003972
locations[1].license
locations[1].pdf_url
locations[1].version	submittedVersion
locations[1].raw_type	info:eu-repo/semantics/article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name
locations[1].landing_page_url	https://hdl.handle.net/11590/469307
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5010111302
authorships[0].author.orcid	https://orcid.org/0000-0002-7602-1524
authorships[0].author.display_name	Patrizio Angelini
authorships[0].countries	IT
authorships[0].affiliations[0].institution_ids	https://openalex.org/I59857034
authorships[0].affiliations[0].raw_affiliation_string	Department of Mathematics, Natural, and Applied Sciences, John Cabot University, Rome, Italy
authorships[0].institutions[0].id	https://openalex.org/I59857034
authorships[0].institutions[0].ror	https://ror.org/01fjdq469
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I59857034
authorships[0].institutions[0].country_code	IT
authorships[0].institutions[0].display_name	John Cabot University
authorships[0].author_position	first
authorships[0].raw_author_name	Patrizio Angelini
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Department of Mathematics, Natural, and Applied Sciences, John Cabot University, Rome, Italy
authorships[1].author.id	https://openalex.org/A5006472576
authorships[1].author.orcid	https://orcid.org/0000-0002-3414-7444
authorships[1].author.display_name	Michael A. Bekos
authorships[1].countries	GR
authorships[1].affiliations[0].institution_ids	https://openalex.org/I194019607
authorships[1].affiliations[0].raw_affiliation_string	Department of Mathematics, University of Ioannina, Ioannina, Greece
authorships[1].institutions[0].id	https://openalex.org/I194019607
authorships[1].institutions[0].ror	https://ror.org/01qg3j183
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I194019607
authorships[1].institutions[0].country_code	GR
authorships[1].institutions[0].display_name	University of Ioannina
authorships[1].author_position	middle
authorships[1].raw_author_name	Michael A. Bekos
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Department of Mathematics, University of Ioannina, Ioannina, Greece
authorships[2].author.id	https://openalex.org/A5006893407
authorships[2].author.orcid	https://orcid.org/0000-0003-2396-5174
authorships[2].author.display_name	Giordano Da Lozzo
authorships[2].countries	IT
authorships[2].affiliations[0].institution_ids	https://openalex.org/I119003972
authorships[2].affiliations[0].raw_affiliation_string	Department of Engineering, Roma Tre University, Rome, Italy
authorships[2].institutions[0].id	https://openalex.org/I119003972
authorships[2].institutions[0].ror	https://ror.org/05vf0dg29
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I119003972
authorships[2].institutions[0].country_code	IT
authorships[2].institutions[0].display_name	Roma Tre University
authorships[2].author_position	middle
authorships[2].raw_author_name	Giordano Da Lozzo
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Department of Engineering, Roma Tre University, Rome, Italy
authorships[3].author.id	https://openalex.org/A5080178526
authorships[3].author.orcid	https://orcid.org/0000-0003-2565-090X
authorships[3].author.display_name	Martin Gronemann
authorships[3].countries	AT
authorships[3].affiliations[0].institution_ids	https://openalex.org/I145847075
authorships[3].affiliations[0].raw_affiliation_string	Algorithms and Complexity Group, TU Wien, Vienna, Austria
authorships[3].institutions[0].id	https://openalex.org/I145847075
authorships[3].institutions[0].ror	https://ror.org/04d836q62
authorships[3].institutions[0].type	education
authorships[3].institutions[0].lineage	https://openalex.org/I145847075
authorships[3].institutions[0].country_code	AT
authorships[3].institutions[0].display_name	TU Wien
authorships[3].author_position	middle
authorships[3].raw_author_name	Martin Gronemann
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	Algorithms and Complexity Group, TU Wien, Vienna, Austria
authorships[4].author.id	https://openalex.org/A5006763389
authorships[4].author.orcid	https://orcid.org/0000-0002-0543-8912
authorships[4].author.display_name	Fabrizio Montecchiani
authorships[4].countries	IT
authorships[4].affiliations[0].institution_ids	https://openalex.org/I27483092
authorships[4].affiliations[0].raw_affiliation_string	Department of Engineering, University of Perugia, Perugia, Italy
authorships[4].institutions[0].id	https://openalex.org/I27483092
authorships[4].institutions[0].ror	https://ror.org/00x27da85
authorships[4].institutions[0].type	education
authorships[4].institutions[0].lineage	https://openalex.org/I27483092
authorships[4].institutions[0].country_code	IT
authorships[4].institutions[0].display_name	University of Perugia
authorships[4].author_position	middle
authorships[4].raw_author_name	Fabrizio Montecchiani
authorships[4].is_corresponding	False
authorships[4].raw_affiliation_strings	Department of Engineering, University of Perugia, Perugia, Italy
authorships[5].author.id	https://openalex.org/A5007335253
authorships[5].author.orcid	https://orcid.org/0000-0001-9192-2067
authorships[5].author.display_name	Alessandra Tappini
authorships[5].countries	IT
authorships[5].affiliations[0].institution_ids	https://openalex.org/I27483092
authorships[5].affiliations[0].raw_affiliation_string	Department of Engineering, University of Perugia, Perugia, Italy
authorships[5].institutions[0].id	https://openalex.org/I27483092
authorships[5].institutions[0].ror	https://ror.org/00x27da85
authorships[5].institutions[0].type	education
authorships[5].institutions[0].lineage	https://openalex.org/I27483092
authorships[5].institutions[0].country_code	IT
authorships[5].institutions[0].display_name	University of Perugia
authorships[5].author_position	last
authorships[5].raw_author_name	Alessandra Tappini
authorships[5].is_corresponding	False
authorships[5].raw_affiliation_strings	Department of Engineering, University of Perugia, Perugia, Italy
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://link.springer.com/content/pdf/10.1007/s00453-023-01180-6.pdf
open_access.oa_status	hybrid
open_access.any_repository_has_fulltext	False
created_date	2023-11-02T00:00:00
display_name	Recognizing Map Graphs of Bounded Treewidth
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	1.0
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W1976784955, https://openalex.org/W2012687409, https://openalex.org/W2889180046, https://openalex.org/W2091382007, https://openalex.org/W1976463682, https://openalex.org/W2029854525, https://openalex.org/W4297435153, https://openalex.org/W1582492864, https://openalex.org/W1585579706, https://openalex.org/W2155351506
cited_by_count	1
counts_by_year[0].year	2023
counts_by_year[0].cited_by_count	1
locations_count	2
best_oa_location.id	doi:10.1007/s00453-023-01180-6
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S89324355
best_oa_location.source.issn	0178-4617, 1432-0541
best_oa_location.source.type	journal
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l	0178-4617
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Algorithmica
best_oa_location.source.host_organization	https://openalex.org/P4310319900
best_oa_location.source.host_organization_name	Springer Science+Business Media
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
best_oa_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-023-01180-6.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Algorithmica
best_oa_location.landing_page_url	https://doi.org/10.1007/s00453-023-01180-6
primary_location.id	doi:10.1007/s00453-023-01180-6
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S89324355
primary_location.source.issn	0178-4617, 1432-0541
primary_location.source.type	journal
primary_location.source.is_oa	False
primary_location.source.issn_l	0178-4617
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Algorithmica
primary_location.source.host_organization	https://openalex.org/P4310319900
primary_location.source.host_organization_name	Springer Science+Business Media
primary_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
primary_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
primary_location.license	cc-by
primary_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-023-01180-6.pdf
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Algorithmica
primary_location.landing_page_url	https://doi.org/10.1007/s00453-023-01180-6
publication_date	2023-10-27
publication_year	2023
referenced_works	https://openalex.org/W4388188757, https://openalex.org/W2070734176, https://openalex.org/W2963368860, https://openalex.org/W2736404189, https://openalex.org/W2944801675, https://openalex.org/W2889102722, https://openalex.org/W2083807544, https://openalex.org/W2007069176, https://openalex.org/W1996472240, https://openalex.org/W1936855748, https://openalex.org/W2294414813, https://openalex.org/W1504740823, https://openalex.org/W2037591624, https://openalex.org/W2778543035, https://openalex.org/W4252763010, https://openalex.org/W2938191358, https://openalex.org/W2903680457, https://openalex.org/W2952421273, https://openalex.org/W2089417393, https://openalex.org/W4292230561, https://openalex.org/W2029448190, https://openalex.org/W2028357390, https://openalex.org/W2914414140, https://openalex.org/W4200514496, https://openalex.org/W4213262063, https://openalex.org/W2964099322, https://openalex.org/W2059372025, https://openalex.org/W2125058377, https://openalex.org/W4213368513, https://openalex.org/W3126614410, https://openalex.org/W2074456731, https://openalex.org/W3101793140, https://openalex.org/W1994887153, https://openalex.org/W3103394879
referenced_works_count	34
abstract_inverted_index.,	144
abstract_inverted_index.A	1, 30, 56
abstract_inverted_index.a	4, 44, 59, 65, 74, 94, 118, 124, 131, 150, 154
abstract_inverted_index.k	36, 45, 143, 151, 156
abstract_inverted_index.It	116
abstract_inverted_index.We	92
abstract_inverted_index.an	90
abstract_inverted_index.as	20, 28
abstract_inverted_index.at	34, 39
abstract_inverted_index.by	89, 103
abstract_inverted_index.if	51, 62, 81, 127, 145
abstract_inverted_index.in	32, 110, 120
abstract_inverted_index.is	3, 43, 49, 58, 64, 108, 130, 136
abstract_inverted_index.it	48, 52
abstract_inverted_index.no	54
abstract_inverted_index.of	6, 73, 113, 123
abstract_inverted_index.or	153
abstract_inverted_index.to	13, 139
abstract_inverted_index.Its	105
abstract_inverted_index.Our	133
abstract_inverted_index.and	70, 82
abstract_inverted_index.any	142
abstract_inverted_index.are	18, 26, 87
abstract_inverted_index.for	98, 141
abstract_inverted_index.its	68
abstract_inverted_index.map	2, 31, 60, 100
abstract_inverted_index.the	7, 23, 40, 71, 84, 111, 114, 121, 128, 146
abstract_inverted_index.two	78
abstract_inverted_index.-map	152
abstract_inverted_index.Some	16
abstract_inverted_index.form	122
abstract_inverted_index.into	9
abstract_inverted_index.map,	75
abstract_inverted_index.most	35
abstract_inverted_index.ones	25
abstract_inverted_index.only	83
abstract_inverted_index.same	41
abstract_inverted_index.size	112
abstract_inverted_index.such	76
abstract_inverted_index.that	77
abstract_inverted_index.time	106
abstract_inverted_index.-map,	46
abstract_inverted_index.-map.	157
abstract_inverted_index.edge.	91
abstract_inverted_index.graph	57, 61, 148
abstract_inverted_index.input	129, 147
abstract_inverted_index.point	42
abstract_inverted_index.test,	140
abstract_inverted_index.there	63
abstract_inverted_index.touch	38, 80
abstract_inverted_index.which	33
abstract_inverted_index.while	22, 47
abstract_inverted_index.admits	149
abstract_inverted_index.closed	14
abstract_inverted_index.disks.	15
abstract_inverted_index.enough	138
abstract_inverted_index.graph.	115
abstract_inverted_index.graphs	101
abstract_inverted_index.holes.	29, 55
abstract_inverted_index.linear	109
abstract_inverted_index.sphere	8
abstract_inverted_index.between	67
abstract_inverted_index.general	137
abstract_inverted_index.labeled	19, 27
abstract_inverted_index.nations	37, 72, 79
abstract_inverted_index.present	93
abstract_inverted_index.regions	11, 17
abstract_inverted_index.reports	117
abstract_inverted_index.Abstract	0
abstract_inverted_index.contains	53
abstract_inverted_index.nations,	21
abstract_inverted_index.vertices	69, 86
abstract_inverted_index.witness,	126
abstract_inverted_index.algorithm	97
abstract_inverted_index.bijection	66
abstract_inverted_index.connected	88
abstract_inverted_index.framework	135
abstract_inverted_index.hole-free	50, 155
abstract_inverted_index.partition	5
abstract_inverted_index.remaining	24
abstract_inverted_index.so-called	125
abstract_inverted_index.tractable	96
abstract_inverted_index.complexity	107
abstract_inverted_index.treewidth.	104
abstract_inverted_index.algorithmic	134
abstract_inverted_index.certificate	119
abstract_inverted_index.recognizing	99
abstract_inverted_index.homeomorphic	12
abstract_inverted_index.corresponding	85
abstract_inverted_index.parameterized	102
abstract_inverted_index.yes-instance.	132
abstract_inverted_index.fixed-parameter	95
abstract_inverted_index.interior-disjoint	10
cited_by_percentile_year.max	94
cited_by_percentile_year.min	89
countries_distinct_count	3
institutions_distinct_count	6
citation_normalized_percentile.value	0.60231842
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False