Dense circuit graphs and the planar Turán number of a cycle Article Swipe

PDF

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2310.06631

The $\textit{planar Turán number}$ $\textrm{ex}_{\mathcal P}(n,H)$ of a graph $H$ is the maximum number of edges in an $n$-vertex planar graph without $H$ as a subgraph. Let $C_k$ denote the cycle of length $k$. The planar Turán number $\textrm{ex}_{\mathcal P}(n,C_k)$ is known for $k\le 7$. We show that dense planar graphs with a certain connectivity property (known as circuit graphs) contain large near triangulations, and we use this result to obtain consequences for planar Turán numbers. In particular, we prove that there is a constant $D$ so that $\textrm{ex}_{\mathcal P}(n,C_k) \le 3n - 6 - Dn/k^{\log_2^3}$ for all $k, n\ge 4$. When $k \ge 11$ this bound is tight up to the constant $D$ and proves a conjecture of Cranston, Lidický, Liu, and Shantanam.

Related Topics

Combinatorics

Planar Transmission Line

Mathematics

Vertex (Graph Theory)

Concepts

Combinatorics Conjecture Planar graph Planar Mathematics Graph Vertex (graph theory) Constant (computer programming) Discrete mathematics Computer science Programming language Computer graphics (images)

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2310.06631
PDF: https://arxiv.org/pdf/2310.06631
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4387561330

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2310.06631

Digital Object Identifier
Title: Dense circuit graphs and the planar Turán number of a cycle

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-10-10

Full publication date if available
Authors: Ruilin Shi, Zach Walsh, Xingxing Yu

List of authors in order
Landing page: https://arxiv.org/abs/2310.06631

Publisher landing page
PDF URL: https://arxiv.org/pdf/2310.06631

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2310.06631

Direct OA link when available
Concepts: Combinatorics, Conjecture, Planar graph, Planar, Mathematics, Graph, Vertex (graph theory), Constant (computer programming), Discrete mathematics, Computer science, Programming language, Computer graphics (images)

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

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4387561330
doi	https://doi.org/10.48550/arxiv.2310.06631
ids.doi	https://doi.org/10.48550/arxiv.2310.06631
ids.openalex	https://openalex.org/W4387561330
fwci
type	preprint
title	Dense circuit graphs and the planar Turán number of a cycle
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
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	0.9965000152587891
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/T11329
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.9902999997138977
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2607
topics[1].subfield.display_name	Discrete Mathematics and Combinatorics
topics[1].display_name	Limits and Structures in Graph Theory
topics[2].id	https://openalex.org/T10996
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9860000014305115
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1704
topics[2].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[2].display_name	Computational Geometry and Mesh Generation
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C114614502
concepts[0].level	1
concepts[0].score	0.8428939580917358
concepts[0].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[0].display_name	Combinatorics
concepts[1].id	https://openalex.org/C2780990831
concepts[1].level	2
concepts[1].score	0.7568581104278564
concepts[1].wikidata	https://www.wikidata.org/wiki/Q319141
concepts[1].display_name	Conjecture
concepts[2].id	https://openalex.org/C101837359
concepts[2].level	3
concepts[2].score	0.7370498180389404
concepts[2].wikidata	https://www.wikidata.org/wiki/Q547823
concepts[2].display_name	Planar graph
concepts[3].id	https://openalex.org/C134786449
concepts[3].level	2
concepts[3].score	0.6655964851379395
concepts[3].wikidata	https://www.wikidata.org/wiki/Q3391255
concepts[3].display_name	Planar
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.6628354787826538
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C132525143
concepts[5].level	2
concepts[5].score	0.5528919696807861
concepts[5].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[5].display_name	Graph
concepts[6].id	https://openalex.org/C80899671
concepts[6].level	3
concepts[6].score	0.496615469455719
concepts[6].wikidata	https://www.wikidata.org/wiki/Q1304193
concepts[6].display_name	Vertex (graph theory)
concepts[7].id	https://openalex.org/C2777027219
concepts[7].level	2
concepts[7].score	0.4195901155471802
concepts[7].wikidata	https://www.wikidata.org/wiki/Q1284190
concepts[7].display_name	Constant (computer programming)
concepts[8].id	https://openalex.org/C118615104
concepts[8].level	1
concepts[8].score	0.3568037748336792
concepts[8].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[8].display_name	Discrete mathematics
concepts[9].id	https://openalex.org/C41008148
concepts[9].level	0
concepts[9].score	0.07377272844314575
concepts[9].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[9].display_name	Computer science
concepts[10].id	https://openalex.org/C199360897
concepts[10].level	1
concepts[10].score	0.0
concepts[10].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[10].display_name	Programming language
concepts[11].id	https://openalex.org/C121684516
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q7600677
concepts[11].display_name	Computer graphics (images)
keywords[0].id	https://openalex.org/keywords/combinatorics
keywords[0].score	0.8428939580917358
keywords[0].display_name	Combinatorics
keywords[1].id	https://openalex.org/keywords/conjecture
keywords[1].score	0.7568581104278564
keywords[1].display_name	Conjecture
keywords[2].id	https://openalex.org/keywords/planar-graph
keywords[2].score	0.7370498180389404
keywords[2].display_name	Planar graph
keywords[3].id	https://openalex.org/keywords/planar
keywords[3].score	0.6655964851379395
keywords[3].display_name	Planar
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.6628354787826538
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/graph
keywords[5].score	0.5528919696807861
keywords[5].display_name	Graph
keywords[6].id	https://openalex.org/keywords/vertex
keywords[6].score	0.496615469455719
keywords[6].display_name	Vertex (graph theory)
keywords[7].id	https://openalex.org/keywords/constant
keywords[7].score	0.4195901155471802
keywords[7].display_name	Constant (computer programming)
keywords[8].id	https://openalex.org/keywords/discrete-mathematics
keywords[8].score	0.3568037748336792
keywords[8].display_name	Discrete mathematics
keywords[9].id	https://openalex.org/keywords/computer-science
keywords[9].score	0.07377272844314575
keywords[9].display_name	Computer science
language	en
locations[0].id	pmh:oai:arXiv.org:2310.06631
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2310.06631
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2310.06631
locations[1].id	doi:10.48550/arxiv.2310.06631
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2310.06631
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5106570612
authorships[0].author.orcid
authorships[0].author.display_name	Ruilin Shi
authorships[0].author_position	first
authorships[0].raw_author_name	Shi, Ruilin
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5112603217
authorships[1].author.orcid
authorships[1].author.display_name	Zach Walsh
authorships[1].author_position	middle
authorships[1].raw_author_name	Walsh, Zach
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5070536551
authorships[2].author.orcid	https://orcid.org/0000-0002-6370-3163
authorships[2].author.display_name	Xingxing Yu
authorships[2].author_position	last
authorships[2].raw_author_name	Yu, Xingxing
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2310.06631
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2023-10-12T00:00:00
display_name	Dense circuit graphs and the planar Turán number of a cycle
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
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	0.9965000152587891
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/W4300899577, https://openalex.org/W3194471551, https://openalex.org/W4375956809, https://openalex.org/W1581373162, https://openalex.org/W2784911598, https://openalex.org/W2010009304, https://openalex.org/W3216105633, https://openalex.org/W2019085620, https://openalex.org/W2990956612, https://openalex.org/W2584131233
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2310.06631
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2310.06631
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2310.06631
primary_location.id	pmh:oai:arXiv.org:2310.06631
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2310.06631
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2310.06631
publication_date	2023-10-10
publication_year	2023
referenced_works_count	0
abstract_inverted_index.-	92, 94
abstract_inverted_index.6	93
abstract_inverted_index.a	7, 24, 52, 83, 116
abstract_inverted_index.$k	102
abstract_inverted_index.3n	91
abstract_inverted_index.In	76
abstract_inverted_index.We	45
abstract_inverted_index.an	17
abstract_inverted_index.as	23, 57
abstract_inverted_index.in	16
abstract_inverted_index.is	10, 40, 82, 107
abstract_inverted_index.of	6, 14, 31, 118
abstract_inverted_index.so	86
abstract_inverted_index.to	69, 110
abstract_inverted_index.up	109
abstract_inverted_index.we	65, 78
abstract_inverted_index.$D$	85, 113
abstract_inverted_index.$H$	9, 22
abstract_inverted_index.$k,	98
abstract_inverted_index.11$	104
abstract_inverted_index.4$.	100
abstract_inverted_index.7$.	44
abstract_inverted_index.Let	26
abstract_inverted_index.The	0, 34
abstract_inverted_index.\ge	103
abstract_inverted_index.\le	90
abstract_inverted_index.all	97
abstract_inverted_index.and	64, 114, 122
abstract_inverted_index.for	42, 72, 96
abstract_inverted_index.the	11, 29, 111
abstract_inverted_index.use	66
abstract_inverted_index.$k$.	33
abstract_inverted_index.Liu,	121
abstract_inverted_index.When	101
abstract_inverted_index.n\ge	99
abstract_inverted_index.near	62
abstract_inverted_index.show	46
abstract_inverted_index.that	47, 80, 87
abstract_inverted_index.this	67, 105
abstract_inverted_index.with	51
abstract_inverted_index.$C_k$	27
abstract_inverted_index.$k\le	43
abstract_inverted_index.bound	106
abstract_inverted_index.cycle	30
abstract_inverted_index.dense	48
abstract_inverted_index.edges	15
abstract_inverted_index.graph	8, 20
abstract_inverted_index.known	41
abstract_inverted_index.large	61
abstract_inverted_index.prove	79
abstract_inverted_index.there	81
abstract_inverted_index.tight	108
abstract_inverted_index.(known	56
abstract_inverted_index.Turán	2, 36, 74
abstract_inverted_index.denote	28
abstract_inverted_index.graphs	50
abstract_inverted_index.length	32
abstract_inverted_index.number	13, 37
abstract_inverted_index.obtain	70
abstract_inverted_index.planar	19, 35, 49, 73
abstract_inverted_index.proves	115
abstract_inverted_index.result	68
abstract_inverted_index.certain	53
abstract_inverted_index.circuit	58
abstract_inverted_index.contain	60
abstract_inverted_index.graphs)	59
abstract_inverted_index.maximum	12
abstract_inverted_index.without	21
abstract_inverted_index.P}(n,H)$	5
abstract_inverted_index.constant	84, 112
abstract_inverted_index.numbers.	75
abstract_inverted_index.number}$	3
abstract_inverted_index.property	55
abstract_inverted_index.Cranston,	119
abstract_inverted_index.Lidický,	120
abstract_inverted_index.P}(n,C_k)	89
abstract_inverted_index.subgraph.	25
abstract_inverted_index.$n$-vertex	18
abstract_inverted_index.P}(n,C_k)$	39
abstract_inverted_index.Shantanam.	123
abstract_inverted_index.conjecture	117
abstract_inverted_index.particular,	77
abstract_inverted_index.connectivity	54
abstract_inverted_index.consequences	71
abstract_inverted_index.$\textit{planar	1
abstract_inverted_index.triangulations,	63
abstract_inverted_index.Dn/k^{\log_2^3}$	95
abstract_inverted_index.$\textrm{ex}_{\mathcal	4, 38, 88
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile