On k-planar Graphs without Short Cycles Article Swipe

PDF

Michael A. Bekos , Prosenjit Bose , Aaron Büngener , Vida Dujmović , Michael M. Hoffmann , Michael Kaufmann , Pat Morin , Saeed Odak , Alexandra Weinberger ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.7155/jgaa.v29i3.3003

We study the impact of forbidding short cycles to the edge density of k-planar graphs; a k-planar graph is one that can be drawn in the plane with at most k crossings per edge. Specifically, we consider three settings, according to which the forbidden substructures are 3-cycles, 4-cycles or both of them (i.e., girth ≥ 5). For all three settings and all k ∈ {1,2,3}, we present lower and upper bounds on the maximum number of edges in any k-planar graph on n vertices. Our bounds are of the form c\sqrt{k}n, for some explicit constant c that depends on k and on the setting. For general k ≥ 4 our bounds are of the form c\sqrt{k}n, for some explicit constant c. These results are obtained by leveraging different techniques, such as the discharging method, the recently introduced density formula for non-planar graphs, and new upper bounds for the crossing number of 2-- and 3-planar graphs in combination with corresponding lower bounds based on the Crossing Lemma.

Related Topics

Not Without My Daughter (Film)

Year Without A Summer

Rebel Without A Cause

Men Without Hats

Not Without My Daughter (Book)

Without A Trace

Translators Without Borders

How To Succeed In Business Without Really Trying (Musical)

Without A Paddle

Without My Daughter

Without Me (Eminem Song)

Eyes Without A Face (Song)

Concepts

No concepts available.

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.7155/jgaa.v29i3.3003
PDF: https://jgaa.info/index.php/jgaa/article/download/3003/3013
OA Status: diamond
OpenAlex ID: https://openalex.org/W4415113082

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.7155/jgaa.v29i3.3003

Digital Object Identifier
Title: On k-planar Graphs without Short Cycles

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-10-13

Full publication date if available
Authors: Michael A. Bekos, Prosenjit Bose, Aaron Büngener, Vida Dujmović, Michael M. Hoffmann, Michael Kaufmann, Pat Morin, Saeed Odak, Alexandra Weinberger

List of authors in order
Landing page: https://doi.org/10.7155/jgaa.v29i3.3003

Publisher landing page
PDF URL: https://jgaa.info/index.php/jgaa/article/download/3003/3013

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: diamond

Open access status per OpenAlex
OA URL: https://jgaa.info/index.php/jgaa/article/download/3003/3013

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4415113082
doi	https://doi.org/10.7155/jgaa.v29i3.3003
ids.doi	https://doi.org/10.7155/jgaa.v29i3.3003
ids.openalex	https://openalex.org/W4415113082
fwci	0.0
type	article
title	On k-planar Graphs without Short Cycles
biblio.issue	3
biblio.volume	29
biblio.last_page	22
biblio.first_page	1
topics[0].id	https://openalex.org/T10996
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9965999722480774
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1704
topics[0].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[0].display_name	Computational Geometry and Mesh Generation
topics[1].id	https://openalex.org/T12162
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9832000136375427
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	Cellular Automata and Applications
topics[2].id	https://openalex.org/T11870
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9672999978065491
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2205
topics[2].subfield.display_name	Civil and Structural Engineering
topics[2].display_name	Structural Analysis and Optimization
is_xpac	False
apc_list
apc_paid
language	en
locations[0].id	doi:10.7155/jgaa.v29i3.3003
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S33451491
locations[0].source.issn	1526-1719
locations[0].source.type	journal
locations[0].source.is_oa	True
locations[0].source.issn_l	1526-1719
locations[0].source.is_core	True
locations[0].source.is_in_doaj	True
locations[0].source.display_name	Journal of Graph Algorithms and Applications
locations[0].source.host_organization
locations[0].source.host_organization_name
locations[0].license	cc-by
locations[0].pdf_url	https://jgaa.info/index.php/jgaa/article/download/3003/3013
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	Journal of Graph Algorithms and Applications
locations[0].landing_page_url	https://doi.org/10.7155/jgaa.v29i3.3003
indexed_in	crossref, doaj
authorships[0].author.id	https://openalex.org/A5006472576
authorships[0].author.orcid	https://orcid.org/0000-0002-3414-7444
authorships[0].author.display_name	Michael A. Bekos
authorships[0].author_position	first
authorships[0].raw_author_name	Michael A. Bekos
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5013674788
authorships[1].author.orcid	https://orcid.org/0000-0002-8906-0573
authorships[1].author.display_name	Prosenjit Bose
authorships[1].author_position	middle
authorships[1].raw_author_name	Prosenjit Bose
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5092709575
authorships[2].author.orcid
authorships[2].author.display_name	Aaron Büngener
authorships[2].author_position	middle
authorships[2].raw_author_name	Aaron Büngener
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5000058655
authorships[3].author.orcid	https://orcid.org/0000-0001-7250-0600
authorships[3].author.display_name	Vida Dujmović
authorships[3].author_position	middle
authorships[3].raw_author_name	Vida Dujmovi´c
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5103088991
authorships[4].author.orcid	https://orcid.org/0000-0001-5307-7106
authorships[4].author.display_name	Michael M. Hoffmann
authorships[4].author_position	middle
authorships[4].raw_author_name	Michael Hoffmann
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5103045561
authorships[5].author.orcid	https://orcid.org/0000-0001-9186-3538
authorships[5].author.display_name	Michael Kaufmann
authorships[5].author_position	middle
authorships[5].raw_author_name	Michael Kaufmann
authorships[5].is_corresponding	False
authorships[6].author.id	https://openalex.org/A5045902784
authorships[6].author.orcid	https://orcid.org/0000-0003-0471-4118
authorships[6].author.display_name	Pat Morin
authorships[6].author_position	middle
authorships[6].raw_author_name	Pat Morin
authorships[6].is_corresponding	False
authorships[7].author.id	https://openalex.org/A5082659766
authorships[7].author.orcid
authorships[7].author.display_name	Saeed Odak
authorships[7].author_position	middle
authorships[7].raw_author_name	Saeed Odak
authorships[7].is_corresponding	False
authorships[8].author.id	https://openalex.org/A5059794692
authorships[8].author.orcid	https://orcid.org/0000-0001-8553-6661
authorships[8].author.display_name	Alexandra Weinberger
authorships[8].author_position	last
authorships[8].raw_author_name	Alexandra Weinberger
authorships[8].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://jgaa.info/index.php/jgaa/article/download/3003/3013
open_access.oa_status	diamond
open_access.any_repository_has_fulltext	False
created_date	2025-10-14T00:00:00
display_name	On k-planar Graphs without Short Cycles
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10996
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9965999722480774
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1704
primary_topic.subfield.display_name	Computer Graphics and Computer-Aided Design
primary_topic.display_name	Computational Geometry and Mesh Generation
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.7155/jgaa.v29i3.3003
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S33451491
best_oa_location.source.issn	1526-1719
best_oa_location.source.type	journal
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	1526-1719
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	True
best_oa_location.source.display_name	Journal of Graph Algorithms and Applications
best_oa_location.source.host_organization
best_oa_location.source.host_organization_name
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://jgaa.info/index.php/jgaa/article/download/3003/3013
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	Journal of Graph Algorithms and Applications
best_oa_location.landing_page_url	https://doi.org/10.7155/jgaa.v29i3.3003
primary_location.id	doi:10.7155/jgaa.v29i3.3003
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S33451491
primary_location.source.issn	1526-1719
primary_location.source.type	journal
primary_location.source.is_oa	True
primary_location.source.issn_l	1526-1719
primary_location.source.is_core	True
primary_location.source.is_in_doaj	True
primary_location.source.display_name	Journal of Graph Algorithms and Applications
primary_location.source.host_organization
primary_location.source.host_organization_name
primary_location.license	cc-by
primary_location.pdf_url	https://jgaa.info/index.php/jgaa/article/download/3003/3013
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	Journal of Graph Algorithms and Applications
primary_location.landing_page_url	https://doi.org/10.7155/jgaa.v29i3.3003
publication_date	2025-10-13
publication_year	2025
referenced_works_count	0
abstract_inverted_index.4	108
abstract_inverted_index.a	15
abstract_inverted_index.c	95
abstract_inverted_index.k	30, 62, 99, 106
abstract_inverted_index.n	82
abstract_inverted_index.We	0
abstract_inverted_index.as	130
abstract_inverted_index.at	28
abstract_inverted_index.be	22
abstract_inverted_index.by	125
abstract_inverted_index.c.	120
abstract_inverted_index.in	24, 77, 155
abstract_inverted_index.is	18
abstract_inverted_index.of	4, 12, 50, 75, 87, 112, 150
abstract_inverted_index.on	71, 81, 98, 101, 162
abstract_inverted_index.or	48
abstract_inverted_index.to	8, 40
abstract_inverted_index.we	35, 65
abstract_inverted_index.2--	151
abstract_inverted_index.5).	55
abstract_inverted_index.For	56, 104
abstract_inverted_index.Our	84
abstract_inverted_index.all	57, 61
abstract_inverted_index.and	60, 68, 100, 142, 152
abstract_inverted_index.any	78
abstract_inverted_index.are	45, 86, 111, 123
abstract_inverted_index.can	21
abstract_inverted_index.for	91, 116, 139, 146
abstract_inverted_index.new	143
abstract_inverted_index.one	19
abstract_inverted_index.our	109
abstract_inverted_index.per	32
abstract_inverted_index.the	2, 9, 25, 42, 72, 88, 102, 113, 131, 134, 147, 163
abstract_inverted_index.∈	63
abstract_inverted_index.≥	54, 107
abstract_inverted_index.both	49
abstract_inverted_index.edge	10
abstract_inverted_index.form	89, 114
abstract_inverted_index.most	29
abstract_inverted_index.some	92, 117
abstract_inverted_index.such	129
abstract_inverted_index.that	20, 96
abstract_inverted_index.them	51
abstract_inverted_index.with	27, 157
abstract_inverted_index.These	121
abstract_inverted_index.based	161
abstract_inverted_index.drawn	23
abstract_inverted_index.edge.	33
abstract_inverted_index.edges	76
abstract_inverted_index.girth	53
abstract_inverted_index.graph	17, 80
abstract_inverted_index.lower	67, 159
abstract_inverted_index.plane	26
abstract_inverted_index.short	6
abstract_inverted_index.study	1
abstract_inverted_index.three	37, 58
abstract_inverted_index.upper	69, 144
abstract_inverted_index.which	41
abstract_inverted_index.(i.e.,	52
abstract_inverted_index.Lemma.	165
abstract_inverted_index.bounds	70, 85, 110, 145, 160
abstract_inverted_index.cycles	7
abstract_inverted_index.graphs	154
abstract_inverted_index.impact	3
abstract_inverted_index.number	74, 149
abstract_inverted_index.density	11, 137
abstract_inverted_index.depends	97
abstract_inverted_index.formula	138
abstract_inverted_index.general	105
abstract_inverted_index.graphs,	141
abstract_inverted_index.graphs;	14
abstract_inverted_index.maximum	73
abstract_inverted_index.method,	133
abstract_inverted_index.present	66
abstract_inverted_index.results	122
abstract_inverted_index.3-planar	153
abstract_inverted_index.4-cycles	47
abstract_inverted_index.Crossing	164
abstract_inverted_index.consider	36
abstract_inverted_index.constant	94, 119
abstract_inverted_index.crossing	148
abstract_inverted_index.explicit	93, 118
abstract_inverted_index.k-planar	13, 16, 79
abstract_inverted_index.obtained	124
abstract_inverted_index.recently	135
abstract_inverted_index.setting.	103
abstract_inverted_index.settings	59
abstract_inverted_index.{1,2,3},	64
abstract_inverted_index.3-cycles,	46
abstract_inverted_index.according	39
abstract_inverted_index.crossings	31
abstract_inverted_index.different	127
abstract_inverted_index.forbidden	43
abstract_inverted_index.settings,	38
abstract_inverted_index.vertices.	83
abstract_inverted_index.forbidding	5
abstract_inverted_index.introduced	136
abstract_inverted_index.leveraging	126
abstract_inverted_index.non-planar	140
abstract_inverted_index.c\sqrt{k}n,	90, 115
abstract_inverted_index.combination	156
abstract_inverted_index.discharging	132
abstract_inverted_index.techniques,	128
abstract_inverted_index.Specifically,	34
abstract_inverted_index.corresponding	158
abstract_inverted_index.substructures	44
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	9
citation_normalized_percentile.value	0.68659187
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True